summaryrefslogtreecommitdiff
path: root/info/mathtrip/src/number.tex
blob: 6e47242313e0e72a25ae4301991d471f6f7c73a6 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
%This command provide the text about number theory in the first column
%of the page 5
%
%The command has one parameter:
%    1) The width of the text
\newcommand\TFiveNumberTheory[1]{%
   \parbox[t]{#1}{%
      \TFiveColOneFontSize
      %Space around math environments
      \DisplaySpace{\TFiveDisplaySpace}{\TFiveDisplayShortSpace}
      %The column is too narrow, ragged rigth is
      %nicer
      \raggedright

      \TFiveTitle{The Chinese remainder theorem:}
      There exists a number $C$ such that:
      \[
      \begin{array}{l%
                    @{\hspace{.1em}}c@{\hspace{.2em}}%
                    l%
                    c%
                    l}
            C & \equiv& r_{1} & \bmod   & m_{1}  \\
              &       &       & \vdots  & \\
            C & \equiv& r_{n} & \bmod   & m_{n} \\
      \end{array}
      \]
      if $m_{i}$ and $m_{j}$ are relatively prime for $i\neq j$.

       \TFiveTitle{Euler's function:}
       $\phi(x)$ is the number of positive integers less than $x$ relatively prime to $x$.

       If $\prod_{i=1}^n p^{e_i}_i$ is the prime factorization of $x$ then
       \begin{DisplayFormulae}{1}{0pt}{3ex plus 1ex minus .5ex}{\SmallChar}{\StyleWithoutNumber}
          \Fm{\phi(x) = \prod_{i=1}^n p^{e_i - 1}_i (p_i - 1)}
       \end{DisplayFormulae}

       \TFiveTitle{Euler's theorem:}
       If $a$ and $b$ are relatively prime then
       \begin{DisplayFormulae}{1}{0pt}{3ex plus 1ex minus .5ex}{\SmallChar}{\StyleWithoutNumber}
          \Fm{1 \equiv a^{\phi(b)} \bmod b}
       \end{DisplayFormulae}

       \TFiveTitle{Fermat's theorem:}
       \begin{DisplayFormulae}{1}{0pt}{3ex plus 1ex minus .5ex}{\SmallChar}{\StyleWithoutNumber}
          \Fm{1 \equiv a^{p-1} \bmod p}
       \end{DisplayFormulae}

       \TFiveTitle{The Euclidean algorithm:}
       if $a > b$ are integers then
       \begin{DisplayFormulae}{1}{0pt}{3ex plus 1ex minus .5ex}{\SmallChar}{\StyleWithoutNumber}
          \Fm{gcd(a, b) = \gcd(a \bmod b, b)}
       \end{DisplayFormulae}

       \AdjustSpace{1.5ex plus .5ex minus 1ex}
       If $\prod_{i=1}^n p^{e_i}_i$ is the prime factorization of $x$ then
       \begin{DisplayFormulae}{1}{0pt}{3ex plus 1ex minus .5ex}{\SmallChar}{\StyleWithoutNumber}
          \Fm{S(x) = \sum_{d\vert x} d = \prod_{i=1}^n \frac{p^{e_i+1}_i - 1}{p_i - 1}}
       \end{DisplayFormulae}

       \TFiveTitle{Perfect Numbers:}
        $x$ is an even perfect number iff $x = 2^{n-1}(2^n - 1)$ and $2^n - 1$ is prime.

       \TFiveTitle{Wilson's theorem:} 
       $n$ is a prime iff $(n-1)! \equiv -1 \bmod n$.

       \TFiveTitle{M\"obius inversion:}
           \mbox{$\mu(i) = \left\{\begin{array}{@{\hspace{.2em plus .05em minus .05em}}l%
                                                @{\hspace{.3em plus .05em minus .05em}}l}
                                  1    & \text{if }i = 1 \\
                                  0    & \text{if $i$ is not square-free} \\
                                  (-1)^r &\text{if $i$ is the product of} \\
                                         &\text{$ir$ distinct primes.} \\
                               \end{array}\right.$}

        If $G(a) = \sum_{d \vert a} F(d)$
        then $F(a) = \sum_{d \vert a} \mu(d) G\Big(\frac{a}{d}\Big)$

      \TFiveTitle{Prime numbers:}
       \begin{DisplayFormulae}{1}{0pt}{3ex plus 1ex minus .5ex}{\SmallChar}{\StyleWithoutNumber}
           %Equation 1
           \def\FirstPart{p_n =}
           \FmPartA{\FirstPart \ln n + n \ln \ln n - n + n \frac{\ln \ln n}{\ln n}+}
           \FmPartB{\FirstPart}{O\left(\frac{n}{\ln n}\right)}
           %Equation 2
           \def\FirstPart{\pi(n) =}
           \FmPartA{\FirstPart\frac{n}{\ln n} + \frac{n}{(\ln n)^2} + \frac{2! n}{(\ln n)^3}+}
           \FmPartB{\FirstPart}{O\left(\frac{n}{(\ln n)^4}\right)}
       \end{DisplayFormulae}
   }
}