Divisors, euclidian algorithms and prime numbers. 除数、欧几里得算法与质数
设 \(m, n \in \mathbb{Z}\) 为两个整数，若 \(m \neq 0\) 且存在整数 \(q \in \mathbb{Z}\) 使得 \(n = qm\)，则称 m 整除 n（记为 \(m | n\)）
称 m 是 n 的除数divisor 、因子factor，或 n 能被 m 整除。当 m 不能整除 n 时，记为
properties of divisors:
- 若 \(a | b\) 且 \(a | c\)，则 \(a | (b + c)\)
- 若 \(a | b\) 且 \(b | c\)，则 \(a | c\)
- 若 \(a | b\)，则对所有 \(k \in \mathbb{Z}\)，有 \(a | bk\)
positive divisor proper divisor， maximal divisor，primer number
设 m 和 n 为正整数，则：
(1) 若 \(m | n\) 且 \(0 < m < n\)，则称 m 是 n 的真除数 proper divisor
(2) 若 m 是 n 的真除数，且不整除 n 的任何其他真除数（即若 \(m | q\) 且 \(q | n\) 对 \(q \in \mathbb{N}\) 成立，则 \(q = n\) 或 \(q = m\)），则称 m 是 n 的极大除数 maximal divisor
(3) 若 \(n \geq 2\) 且除 1 外无其他真除数，则称 n 为质数
n is prime if n ≥ 2 and n has no proper divisor other than 1
推论 11：两个非零整数互质的充要条件是它们没有公共质因数
定理 10：
设 \(n = p_1^{r_1} \cdots p_s^{r_s}\)（其中 \(p_1, \cdots, p_s\) 为不同质数，\(r_i \geq 1\)（\(i = 1, \cdots, s\)）），则：
- n 的所有（正）除数为 \(p_1^{l_1} \cdots p_s^{l_s}\)（其中 \(0 \leq l_i \leq r_i\)（\(i = 1, \cdots, s\)））；
- n 的正除数个数为 \((r_1 + 1) \cdots (r_s + 1)\)
- r 的含义是：是 n 的质因数分解里各个质因子的指数n=360=2³・3²・5¹，所以 r₁=3，r₂=2，r₃=1正因数个数 =(3+1)(2+1)(1+1)=24
- n的真除数个数为 \((r_1+1)\cdots(r_s+1)-1\)
- n 的极大除数等于n分解的“不同质数因子” 的个数，分别为 \(m_i = \frac{n}{p_i}\)（\(i = 1, \cdots, s\)）
例题：How many proper divisors does 100 have? Find all its maximal divisors.
Estimating the number of primes 质数个数估算
用 \(|S|\) 表示 S 有限集合中元素的个数，可以用下面的定理估计 小于 m 的素数个数
\({\pi(m)}\) 把所有 小于 m的素数的数量
例：\(\pi(10) = 4\)，因为小于 10 的素数是 2, 3, 5, 7，10/ln10 =4.343
这些估算虽不够精确，但能提供合理的 “大致范围”，足以用于估算寻找质数的时间
The division algorithm
设 \(a, b \in \mathbb{Z}\) 且 \(b > 0\)，则存在唯一整数 \(q, r\) 满足 \(0 \leq r < b\)，使得 \(a = qb + r\)。
例题：
欧几里得算法Euclidean algorithm求最大公约数greatest common divisor
最大公约数：设 a 和 b 为两个非负整数，且不同时为零。则它们的最大公约数（记为 \(gcd(a, b)\)）是满足 \(c | a\) 且 \(c | b\) 的最大整数 c
下述算法通过反复使用除法算法求两个整数的最大公约数：设 \(a \geq b \geq 0\) 为非负整数，反复应用除法算法可得：
\(a = q_1b + r_1\)，其中 \(0 \leq r_1 < b\)
\(b = q_2r_1 + r_2\)，其中 \(0 \leq r_2 < r_1\)
\(\cdots\)
\(r_k = q_{k+2}r_{k+1} + r_{k+2}\)，其中 \(0 \leq r_{k+2} < r_{k+1}\)
\(\cdots\)
\(r_{n-2} = q_nr_{n-1} + 0\)
由于余数序列 \(r_1 > r_2 > \cdots\) 严格递减，有限步后会得到 \(r_n = 0\)，此时 \(gcd(a, b) = r_{n-1}\)
欧几里得算法的一个推论：设 a 和 b 为正整数，则存在整数 \(x, y \in \mathbb{Z}\) 使得 \(gcd(a, b) = xa + yb\)
例题：
求 \(gcd(204, 81)\)。并找出整数 \(x, y \in \mathbb{Z}\) 使得 \(gcd(204, 81) = 204x + 81y\)
习题 3
- 用欧几里得算法求 \(gcd(186, 108)\)，并找出整数 \(a, b\) 使得 \(186a + 108b = gcd(186, 108)\)
- 再找出另一对整数 \(a_1, b_1\) 使得 \(186a_1 + 108b_1 = gcd(186, 108)\)
- 证明存在无穷多对（互不相同）整数 \(a_n, b_n\) 使得 \(186a_n + 108b_n = gcd(186, 108)\)
定义 4：若非零整数 \(a, b \in \mathbb{Z}\) 满足 \(gcd(a, b) = 1\)，则称 a 和 b 互质（或互素）coprime or relatively prime
推论 3：设 \(a, b \in \mathbb{Z}\)，则 a 和 b 互质的充要条件是存在 \(x, y \in \mathbb{Z}\) 使得 \(ax + by = 1\)
推论 4：设 \(a, b \in \mathbb{Z}\) 为非零整数，则 \(\frac{a}{gcd(a, b)}\) 和 \(\frac{b}{gcd(a, b)}\) 互质
推论 5：设 \(a, b\) 为非零整数，若 \(a | c\)、\(b | c\) 且 \(gcd(a, b) = 1\)，则 \(ab | c\)
GCD (n, 0) 的结果等于 | n|（n 的绝对值）
这是因为 “最大公约数” 的定义是 “能同时整除两个数的最大正整数”，而任何非零整数都能整除 0
Linear diophantine equations and applications 线性丢番图方程及其应用
定义 5：二元线性丢番图方程是形如 \(ax + by = c\) 的方程，其中 \(a, b, c \in \mathbb{Z}\)，\(x, y\) 为仅取整数值的变量
该方程称为 “线性” 是因其图像为直线；指变量限制为整数
Example 11. Find integer solutions \(x, y \in \mathbb{Z}\) to the equation \(114x + 42y = 660\)
Example 12. Show that there are no integer solutions \(x, y \in \mathbb{Z}\) to \(21x + 35y = 900\).
质因数分解 Prime factorisation.
命题 3（欧几里得引理）：设 p 为质数，\(a, b\) 为非负整数，若 \(p | ab\)，则 \(p | a\) 或 \(p | b\)。
定理 9（算术基本定理）：每个整数 \(n > 1\) 都可表示为质数的乘积；该表示除因子的顺序外唯一。
Example 14. Find prime factorisations of 201, 1001, 4725, 7007. 找出 201、1001、4725、7007 的质因数分解
尽量用小质数试除（2, 3, 5, 7…）或识别特殊形式\(2^n – 1\)（如 1023, 2047）
