Lemma 23. The following statements about divisibility hold.
- If
$a\mid b$ , then$a\mid bc$ for all$c$ .- If
$a\mid b$ and$b\mid c$ , then$a\mid c$ .- If
$a\mid b$ and$a\mid c$ , then$a\mid sb+tc$ for all$s$ and$t$ .- For all
$c \neq 0$ ,$a\mid b$ if and only if$ca\mid cb$ .
质数是大于1的除了1和其本身不被其它数整除的数.
Theorem 24. Let
$p$ be a prime. If$p \mid a_1a_2 ... a_n$ , then$p$ divides some$a_i$ .
除数和余数的唯一性:
Theorem 25 (Division Algorithm). Let
$n$ and$d$ be integers such that$d > 0$ . Then there exists a unique pair of integers$q$ and$r$ such that$n = qd + r$ and$0 ≤ r < d$ .
余数被记做
高斯定义
Lemma 26.
$a\equiv b (mod\ c)$ if and only if$(a\ rem\ c)=(b\ rem\ c)$
$a\equiv b(mod\ n)$ implies$a+c\equiv b+c (mod\ n)$
Lemma 27.
- If
$a_1\equiv b_1(mod\ n)$ and$a_2\equiv b_2(mod\ n)$ , then$a_1 a_2\equiv b_1 b_2(mod\ n)$ .$a\ rem\ n \equiv a (mod\ n)$ .$(a_1\ rem\ n) \cdot (a_2\ rem\ n) \cdots (a_k\ rem\ n) \equiv a_1 \cdot a_2 \cdots a_k (mod\ n)$ .
Lemma 28.
Suppose$p$ is a prime and$k$ is not a multiple of$p$ . If$a k \equiv b k\ (mod\ p)$ then$a\equiv b\ (mod\ p)$ .
Corollary 29. Suppose p is a prime and k is not a multiple of p. Then the sequence:
$(0\cdot k)\ rem\ p, (1\cdot k)\ rem\ p, (2\cdot k)\ rem\ p, \cdots, (p−1)\cdot k\ rem\ p$
is a permutation of the sequence:
$0, 1, 2, \cdots, (p−1)$
This remains true if the first term is deleted from both sequence.
Corollary 30. Let
$p$ be a prime. If$k$ is not a multiple of$p$ , then there exists an integer $ k^{−1} \epsilon \{1, 2, \cdots, p − 1\}$ such that$k \cdot k^{−1} \equiv 1\ (mod\ p)$ .
Theorem 31 (Fermat’s Theorem). Suppose
$p$ is a prime and$k$ is not a multiple of$p$ . Then:$k^{p−1} \equiv 1\ (mod\ p)$ .
根据费马小定理求乘法逆元:
Theorem 35.
$gcd(a,b)$ is equal to the smallest positive linear combination of$a$ and$b$ .
Corollary 36. Every linear combination of
$a$ and$b$ is a multiple of$gcd(a, b)$ and vice versa.
最大公约数的一些性质:
Lemma 38. The following statements about the greatest common divisor hold:
- Every common divisor of
$a$ and$b$ divides$gcd(a, b)$ .$gcd(ka,kb)=k \cdot gcd(a,b)$ for all$k>0$ .- If
$gcd(a,b) = 1$ and$gcd(a,c) = 1$ , then$gcd(a,bc) = 1$ .- If
$a \mid bc$ and$gcd(a,b)=1$ ,then$a \mid c$ .$gcd(a, b) = gcd(a\ rem\ b, b)$ (Euclid’s algorithm).
Every positive integer
$n$ can be written in a unique way as a product of primes:
$n = p1 \cdot p2 \cdots pj\ (p1 \leq p2 \leq \cdots \leq pj)$
需要强调两点:
- 1不能算质数
- 0个质数相乘结果应该记为1
Lemma 40. If
$p$ is a prime and$p \mid ab$ , then$p \mid a$ or$p \mid b$ .
Lemma 41. Let$p$ be a prime. If$p \mid a_1 a_2 \cdots a_n$ , then$p$ divides some$a_i$ .
a 和 b 互质当且仅当
欧拉函数
Theorem 42. The function
$\phi$ obeys the following relationships:
- If
$a$ and$b$ are relatively prime, then$\phi(ab) = \phi(a)\phi(b)$ .- If
$p$ is a prime, then$\phi(p^k)=p^k −p^{k−1}$ for$k\geq 1$ .
Lemma 43. Let
$n$ be a positive integer. If$k$ is relatively prime to$n$ , then there exists an integer$k^{−1}$ such that$k \cdot k^{−1} \equiv 1\ (mod\ n)$ .
Corollary 44. Suppose
$n$ is a positive integer and$k$ is relatively prime to$n$ . If$ak \equiv bk\ (mod\ n)$ then$a \equiv b\ (mod\ n)$ .
a generalization of Fermat’s Theorem to an arbitrary modulus
Lemma 45. Suppose
$n$ is a positive integer and$k$ is relatively prime to$n$ .
Let$k_1, \cdots, k_r$ denote all the integers relatively prime to n in the range$0 \leq k_i \lt n$ .
Then the sequence:
$(k_1 \cdot k)\ rem\ n, (k_2 \cdot k)\ rem\ n, (k_3 \cdot k)\ rem\ n, \cdots, (k_r \cdot k)\ rem\ n$
is a permutation of the sequence:
$k_1, k_2, \cdots, k_r$
Then
Theorem 46 (Euler’s Theorem). Suppose
$n$ is a positive integer and$k$ is relatively prime to$n$ . Then:$k^{\phi(n)} \equiv 1\ (mod\ n)$
We can find multiplicative inverses using Euler’s theorem as we did with Fermat’s theorem: if