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}
}
}
|
