记号: 整数集 `ZZ`, 非零整数集 `ZZ^**`, 正整数集 `ZZ^+`. 以下若无特殊说明, `a, b, c, m, n` 等均表示整数.
设 `n, d` 为整数, 若存在整数 `k` 使得 `n = k d`, 则记 `d | n`, 读作 `d` 整除 `n`. 我们也说 `d` 是 `n` 的因子 (factor) 或约数 (denominator) 或除数 (divisor), 也可以说 `n` 是 `d` 的倍数. 若 `d` 不能整除 `n`, 则记 `d !| n`.
对任意整数 `d`, `d | 0` 总是成立; 若 `0 | n`, 则 `n = 0`.
`(AA k in ZZ^**)` `a | b` `iff k a | k b`.
`a | b rArr |a| le |b|` 或 `b = 0`. 这表明非零整数的因子只有有限个. 此外, 这个结论还用于带余除法的证明中.
设 `b = k a`, 且 `b != 0`. 这推出 `k != 0`, 因此 `|k| ge 1`, 从而 `|b| = |k| |a| ge |a|`.
只证 3. 若 `a = 0`, 由 `a | b` 知 `b` 也等于零, 结论自然成立; `b = 0` 时同理. 下设 `a, b` 都不为零, 由有 `|a| le |b|`, `quad |b| le |a|`, 因此结论成立.
设 `b in ZZ^**`, 它的全体 (正) 因子是 `{d_1, d_2, cdots, d_k}`, 则 `{b//d_1, b//d_2, cdots, b//d_k}` 也是它的全体 (正) 因子.
只证结论一, 结论二类似. 设 `d_i | b`, 则 `b = d_i (b // d_i)`, 且 `b//d_i in ZZ^**`. 所以 `b//d_i | b`. 另一方面, `d_i != d_j` 时, 有 `b//d_i != b//d_j`. 所以 `b//d_1, b//d_2, cdots, b//d_k` 是 `b` 的 `k` 个不同的因子, 即为 `b` 的全体因子.
若 `d | a`, `d | b`, 则 `d` 称为 `a, b` 的公约数. `a, b` 不全为零时, 它们的公约数只有有限个, 我们称其中最大的为 `a, b` 的最大公约数 (greatest common divisor), 记为 `gcd(a, b)` 或 `(a, b)`; 为使最大公约数的性质普遍成立, 我们规定 `(0, 0) = 0`.
若 `a | h`, `b | h`, 则 `h` 称为 `a, b` 的公倍数. `a, b` 中有一个为零时, 平凡地有 `h = 0`; 若 `a, b != 0`, 则 `a, b` 的全体公倍数中存在最小正整数, 称为 `a, b` 的最小公倍数 (least common multiple), 记为 `lcm(a, b)` 或 `[a, b]`.
类似可以定义 `n` 个整数 `a_1, a_2, cdots, a_n` 的 (最大) 公约数和 (最小) 公倍数. 本节的许多结论容易推广到任意有限个整数的情形, 简明起见不再赘述.
利用, 反复将一个数的 `k` 倍加到另一数上, 就可以化简关系, 从而求出最大公约数. 这种做法为后面的辗转相除法提供了思想. 一例: `(-30; 45; -84)` `rarr (30; 45; 84)` `rarr (30; 15; 24)` `rarr (0; 15; 9)` `rarr (0; 6; 9)` `rarr (0; 6; 3)` `rarr (0; 0; 3)` 从而 (-30, 45, 84) = 3.
为进一步揭示最大公约数的性质, 我们引入有力工具——带余除法.
带余除法 设 `n in ZZ`, `d in ZZ^**`, 则存在唯一的整数 `q` 与 `r`, 满足 `n = q d + r`, `quad 0 le r lt |d|`. 且 `d | n` 当且仅当 `r = 0`.
带余除法中, `n, d, q, r` 分别称为被除数, 除数, 商和余数. 带余除法是证明 `d | n` 这类命题的重要工具.
`a, b` 的公约数整除 `a, b` 的任意线性组合: `d | a and d | b` `iff (AA x, y in ZZ)` `d | a x + b y`.
`lArr` 分别取 `(x, y) = (1, 0)` 和 `(0, 1)` 即可;
`rArr` 设 `a = d a_1`, `b = d a_2`, 则
`a x + b y = d (a_1 x + b_1 y)`.
Bezout (裴蜀) 定理 设整数 `a, b` 不全为零, 则 `(a, b)` 是 `a, b` 的全体线性组合 `S = {a x+b y: x, y in ZZ}` 中的最小正整数.
`(a, b)` 是 `a, b` 的公约数集的最大元, 又是线性组合集的最小元, 这样的对偶关系值得玩味.
可以用 2. 来证 1.
`lArr` 显然, 下证 `rArr`. 记 `g = (a, b)`,
`h` 是 `a, b` 的全体公约数的最小公倍数.
一方面, 由于 `g` 也是 `a, b` 的公约数, 有 `g | h`,
这推出 `g le h`;
另一方面, `a` 是 `a, b` 的全体公约数的一个公倍数, 由 1 有 `h | a`.
同理 `h | b`. 这说明 `h` 是 `a, b` 的公约数, 故 `h le g`.
综上 `g = h`, 即最大公约数是全体公约数的最小公倍数.
由 Bezout 定理, `a, b` 互素当且仅当 1 是它们的线性组合, 即存在整数 `x, y` 使 `a x + b y = 1`.
必要性显然, 下证充分性. 由于 1 是 `a, b` 的线性组合, 故 `a, b` 的所有线性组合中的最小正整数是 1, 即 `(a, b) = 1`.
2. 的另一证明: 利用 Bezout 定理, 设 `1 = a x + b y`, `x, y` 为整数. 从而 `a | a n x + b n y = n`.
设 `a, b` 是正整数, 则 `(a, b) [a, b] = a b`.
记 `d = (a,b)`, `l = [a,b]`.
一方面 `a | (a b)/d`, `b | (a b)/d`, 所以 `(a b)/d` 是 `a, b`
的公倍数, 有 `l | (a b)/d`.
另一方面
由 `d(a/d, b/d) = (a, b) = d` 知 `(a/d, b/d) = 1`.
而 `a/d | l/d`, `b/d | l/d`, 所以 `(a b)/d^2 | l/d`,
即 `(a b)/d | l`.
求 `(18, 25) = d`, 并找到 `x, y` 满足等式 `18 x + 25 y = d`.
25 = (0, 1) 18 = (1, 0) 7 = (-1, 1) 4 = (3, -2) 3 = (-4, 3) 1 = (7, -5)因此 `18 * 7 - 25 * 5 = 1`.
拉梅定理 Fibonacci 数定义为 `F_0 = F_1 = 1`, `quad F_(n+2) = F_(n+1) + F_n`. 正整数 `a gt b` 进行辗转相除, 若 `a // b` 的余数 `r_1 le F_n`, 则除法的运算次数不超过 `n+1`.
记第 `n` 次除法的余数为 `r_n`. 假设恰好作了 `n+1` 次除法,
即 `r_(n+1) = 0`, 注意到辗转相除法中余数严格单调递减, 有
`r_n ge 1 = F_1`,
`r_(n-1) ge r_n+1 ge 2 = F_2`,
`r_(n-2) = r_(n-1) + r_n ge F_3`.
依此类推, 由归纳法得 `r_1 ge F_n`. 又注意到 `r_1 = F_n` 时,
上式各等号均成立, 因此当 `a, b` 是相邻的 Fibonacci 数时为辗转相除法的最坏情形.
于是 `r_1 le F_n` 时, 算上第一次得到 `r_1` 时所作的除法, 除法的运算次数不超过 `n+1`.
设 `n in ZZ`. 显然 `+-1, +-n` 是 `n` 的因子, 称为平凡因子.
`n` 的其他因子称为非平凡因子或真因子.
设 `n gt 1`, 如果 `n` 只有平凡因子, 则称它是素数 (prime
number); 否则称它是合数 (composite number).
100 以内的素数有 25 个 (阴影部分):
合数必有素因子.
设 `T` 是合数 `n` 的全体非平凡正因子的集合, 由定义 `T != O/`. 由最小自然数原理, `T` 中有最小元素 `p`. 若 `p` 是合数, 则 `p` 有非平凡因子 `d`, `1 lt d lt p`. 显然 `d in T`, 这与 `p` 是 `T` 的最小元素矛盾. 故 `p` 是素数.
算术基本定理 (唯一因子分解定理) 任意整数 `n gt 1` 可以表为素因子的乘积 `n = prod_(i=1)^s p_i`, 其中 `p_i` 是素数, `i = 1, 2, cdots, s`, 不计素因子次序, 这种分解是唯一的. 如果将相同的素因子合并, 上式可写为标准分解式 `n = prod_(i=1)^l p_i^(m_i)`, 其中 `m_i in NN` 是重数, `i = 1, 2, cdots, l`. 换言之, 任意整数 `n gt 1` 都唯一对应着一个素数的多重集合 `{p_1: m_1, p_2: m_2, cdots, p_l: m_l}`.
算术基本定理是本章的主要结果, 也是数学中最重要和最基本的定理之一. 在此后我们还要对它做进一步讨论. 这里先证明存在性, 唯一性留待以后证明.
先证存在性. 当 `n = 2` 时, 2 是素数, 所以结论成立. 假设结论对任意整数 `1 lt a lt n` 都成立, 考虑 `n` 的情形. 若 `n` 是素数, 结论已经成立; 若 `n` 是合数, 则由, 存在整数 `1 lt n_1, n_2 lt n` 使得 `n = n_1 n_2`. 由归纳假设, `n_1, n_2` 有素因子分解 `n_1 = prod_(i=1)^s p_i`, `quad n_2 = prod_(i=1)^t q_i`. 于是 `n = p_1 p_2 cdots p_s q_1 q_2 cdots q_t`. 由第二数学归纳法, 存在性得证.
Eratoschenes 筛法, Euler 筛法: 参看计算机笔记.
素数有无穷多个.
反设素数有限, 为 `p_1, p_2, cdots, p_n`. 考虑 `a = prod_(i=1)^n p_i + 1`, 显然 `a` 大于任意一个素数, 因此是合数. 由, `a` 有素因子 `p | a`. 设 `p = p_j`, 则 `p = p_j | a - prod_(i=1)^n p_i = 1`, 与 `p ge 2` 矛盾.
今后我们会介绍 `p_n` 与 `pi(n)` 的更好的估计.
Frobenius 自同构 ?? 对任意整数 `a, b`, 素数 `p` 和非负整数 `n` 有 `(a+b)^(p^n) -= a^(p^n) + b^(p^n) (mod p)`, 特别 `(a+b)^p -= a^p + b^p (mod p)`.
利用 Fermat 小定理计算 `2^100` 除以 `13` 的余数.
这里 `p = 13`. 由 Fermat 小定理, `2^12 -= 1` `(mod 13)`. `2^100 -= 2^(12 xx 8 + 4)` `-= (2^12)^8 * 2^4` `-= 2^4 -= 3` `(mod 13)`.
`AA a in NN`, `2730 | a^13-a`.
设 `d | 12`, 则 `a^d-1 | a^12-1`. 若 `d = p-1`, `p` 为素数, 由 Fermat 小定理有 `p | a^p-a` `= a(a^d-1) | a(a^12-1)`. 列出 12 的所有正因数 1, 2, 3, 4, 6, 12, 再分别加 1 得 2, 3, 4, 5, 7, 13, 其中素数有 2, 3, 5, 7, 13. 所以 `2730 = 2 xx 3 xx 7 xx 13 | a^13-a`.
对任意整数 `n`, `15 | 3n^5+5n^3+7n`.
由 Fermat 小定理, `n^p - n -= 0 (mod p)`. 于是
`3n^5+5n^3+7n -= 5(n^3-n) + 5n + 7n -= 0 (mod 3)`,
`3n^5+5n^3+7n -= 3(n^5-n) + 3n + 7n -= 0 (mod 5)`.
[来自 KummerTheoremLucasTheorem]
若素数 `p` 和正整数 `n` 满足 `p^k | n`, `p^(k+1) !| n`, 则称 `p` 在 `n` 中的次数是 `k`, 或者称 `n` 的 `bm p` 进制值 (`bm p`-adic valuation) `v_p(n) = k`. 显然 `v_p` 是积性函数, 满足 `v_p(m n) = v_p(m) v_p(n)`.
`n!` 末尾有多少个零?
即求 `5` 在 `n!` 中的次数. 因为 `n` 以内的正整数中, `5` 的倍数有 `|__n/5__|` 个, 它们为乘积 `n!` 提供了 `|__n/5__|` 个 `5` 的因子. 在这些 `5` 的倍数中, `5^2` 的倍数有 `|__n/5^2__|` 个, 为乘积 `n!` 提供了额外的 `|__n/5^2__|` 个 `5` 的因子. 依次类推, `n!` 中, `5` 的次数等于 `sum_(i ge 1) |__n/5^i__|`. 上式是无穷级数, 但只有有限项不为零.
Legendre 公式 `p` 为素数, 将正整数 `n` 写为 `p` 进制 `n = sum_(i=0)^k a_i p^i`, 记 `s_p(n) = sum_(i=0)^k a_i`, 有 `v_p(n!) = (n - s_p(n))/(p-1)`.
`v_p(n!) = sum_(i ge 1) |__n/p^i__|` `= (a_1 + cdots + a_k p^(k-1))` `+ (a_2 + cdots + a_k p^(k-2))` `+ cdots + a_k` `= a_1 + a_2 (1+p) + cdots + a_k(1+p+cdots+p^(k-1))` `= [a_1(p-1) + a_2(p^2-1) + cdots + a_k(p^k-1)]//(p-1)` `= (n - s_p(n))/(p-1)`.
Kummer 定理 `p` 为素数, 将 `m, n` 写为 `p` 进制数然后相加, 进位的次数恰等于 `v_p(m+n;n)`.
记 `m+n = sum_(i=0)^r a_i p^i`, `quad m = sum_(i=0)^r b_i p^i`, `quad n = sum_(i=0)^r c_i p^i`, 如果三个数的位数不同, 可以在 `m, n` 的开头补零使它们相同. 定义进位函数 `gamma` 如下: `gamma_(-1) = gamma_r = 0`, `0 le i lt r` 时, `gamma_i = { 1, if b_i + c_i + gamma_(i-1) ge p; 0, otherwise; :}` 根据加法法则, 我们有 `a_i = b_i + c_i + gamma_(i-1) - p gamma_i`, `quad i = 0, cdots, r`. 求和得 `s_p(m+n) - s_p(m) - s_p(n)` `= sum_(i=1)^r gamma_(i-1) - sum_(i=0)^(r-1) p gamma_i` `= (1-p) sum_(i=0)^(r-1) gamma_i`. 现在应用 Legendre 公式有 `v_p (m+n; n)` `= v_p((m+n)!) - v_p(m!) - v_p(n!)` `= (s_p(m) + s_p(n) - s_p(m+n))/(p-1)` `= sum_(i=0)^(r-1) gamma_i`, 这正是进位的次数.
Lucas 定理 `p` 为素数, 计算 `(m; n) mod p`. 先将 `m, n` 写为 `p` 进制数: `m = sum_(i=0)^k a_i p^i`, `quad n = sum_(i=0)^k b_i p^i`, 则有 `(m; n) -= prod_(i=0)^k (a_i; b_i) (mod p)`. 特别 `(m; n)` 是奇数当且仅当它们的二进制表示满足 `a_i ge b_i`, `i = 0, cdots, k`.
考虑 `(1+x)^m` 的 `n` 次项系数 `(m; n)`, 利用 Frobenius 引理有 `(1+x)^m` `= (1+x)^(sum_(i=0)^k a_i p^i)` `= prod_(i=0)^k (1+x)^(a_i p^i)` `-= prod_(i=0)^k (1+x^(p^i))^(a_i)` `= prod_(i=0)^k sum_(j_i=0)^(a_i) (a_i; j_i) x^(j_i p^i) (mod p)`. 考虑上式右端的 `n` 次项系数, 这只需从乘积的因子中各取一项 `(a_i; j_i) x^(j_i p^i)` 相乘即可. 它们的次数之和满足 `sum_(i=0)^k p^i j_i = n`. 由 `p` 进制表示的唯一性知道 `j_i = b_i`, `i = 0, cdots, k`, 于是所求的 `n` 次项系数是 `prod_(i=0)^k (a_i; b_i) (mod p)`.
设 `n in NN\\{1}`, `0 le r lt n`. 记全体模 `n` 余数等于 `r` 的整数为 `S_(n,r) = {kn + r: k in ZZ}`. 我们有 `uuu_(r=0)^(n-1) S_(n,r) = ZZ`; `quad` `S_(n,r_1) nn S_(n,r_2) = O/`, `r_1 != r_2`. 即全体整数按模 `n` 的余数分为 `n` 个类, 称为模 `n` 的同余类. 在每一同余类中的数模 `n` 后有相同余数, 称它们模 `n` 同余, 记为 `a -= b (mod n)`. 显然 `a -= b (mod n) iff n | a - b`.
除以 7, 11, 13 的余数 一个前三位和后三位数字完全相同的六位数 (如, 123123) 显然是 1001 的倍数. 注意到 `1001 = 7 xx 11 xx 13`, 因此我们可以反复从一个数中减去 1001 的倍数, 来计算这个数除以 7 (或 11, 13) 的余数. 如考虑 142857, 有 `142857 -= 142857 - 142142 -= 715 -= 1 (mod 7)`. 类似地, 利用 `17 | 10^8+1` 可以计算除以 17 的余数, 只不过计算量更大了.
设 `a in NN\\{1}`, `n in NN`. 则 `n` 可以唯一地表为 `n = sum_(i=0)^m r_i a^i`, `quad` `m ge 0`, `0 le r_i lt a`, `i = 0, 1, cdots, m`. 称为正整数 `n` 的 `a` 进位 (base-`a` 或 radix-`a`) 表示.
由最大自然数原理, 对正整数 `n` 存在唯一的 `m ge 0`, 使 `a^m le n lt a^(m+1)`. 由带余除法, 存在唯一的 `q, r` 满足 `n = a q + r`, `quad 0 le r lt a`. 对 `m` 使用数学归纳法. 若 `m = 0`, 则必有 `q = 0`, `1 le r lt a`, 所以结论成立. 设结论对整数 `m ge 0` 成立, 考虑 `m+1` 的情形. 因为 `a^(m+1) le n lt a^(m+2)`, 所以上式中的 `q` 满足 `a^m le q lt a^(m+1)`. 由归纳假设, 存在唯一的 `0 le s_i lt a`, `i=0,1,cdots,m`, 使 `q = sum_(i=0)^m s_i a^i`. 所以 `n = a sum_(i=0)^m s_i a^i + r = r + sum_(i=1)^(m+1) s_(i-1) a^i`, 即结论对 `m+1` 成立.