030 Primes and Greatest Common Divisors

Primes

定义 1 如果大于 1 的整数 $p$ 只有两个因子 1 和 $p$，那么 $p$ 是质数。大于 1 的非质数称为合数。

注意，1 不是质数，因为只有 1 一个因子。$n$ 是合数等价于存在一个 $a$ 使得 $a|n,1<a<n$。

定理 1 算术基本定理 每一个大于 1 的整数，要么是一个质数，要么能唯一的按照非递减序写成两个或者更多的质数之积。

Trial Division

定理 2 如果 $n$ 是一个合数，那么存在一个质因数小于等于 $\sqrt{n}$。

证明：根据合数定义，存在一个 $a,1<a<n$ 是 $n$ 的因数，那么存在 $b,1<b<n$ 使得 $ab=n$。反证法。假设 $a,b$ 都大于 $\sqrt{n}$，那么 $ab>\sqrt{n}\sqrt{n}>n$，矛盾，所以至少存在一个因数小于等于 $\sqrt{n}$。不妨设 $a<b$，如果 $a$ 是质数，证明完成。如果 $a$ 是合数，根据算术基本定理，那么存在一个小于 $a$ 的质因数，证明完成。

根据定理 2，如果一个整数能够被小于等于它的所有质数整除，那么这个整数是质数。这个判断一个数是否是质数的方法称为试除法。

下面的过程可以用于找到一个整数的质因数。从最小的质数 2 开始使用各个质数试除 $n$。如果 $n$ 包含质因数，那么根据定理 2 存在一个不超过 $\sqrt{n}$ 的质数 $p$ 能够整数 $n$。如果找到到这样的 $p$，说明 $n$ 是质数，结束整个过程；否则继续寻找 $n/p$ 的质因数。注意，$n/p$ 不存在比 $p$ 小的质因数，所以这里从 $p$ 开始即可。

The Sieve of Eratosthenes

埃拉托斯特尼筛法用于找到所有不超过指定的某个整数的所有质数。从 2 开始，将比 2 大且能被 2 整除的数都删除。下一个没有被删除的数是质数，这里是 3，然后将比 3 大且能被 3 整除的数都删除。下一个没有被删除的数是质数，是 5。依次类推。

很早之前人们就意识到质数无穷多。给定前 $n$ 小的质数 $p_1,p_2,\cdots,p_n$，存在一个更大的质数不在此列。欧几里得就给出一个非常优雅的证明。

定理 3 存在无数个质数。

证明：反证法。假设只有有限多个质数 $p_1,p_2,\cdots,p_n$，令 $$Q=p_1p_2\cdots p_n+1$$ 根据算术基本定理，$Q$ 是质数或者是能分解成两个或多个质数的乘积。假定存在某个 $p_j|Q$，那么 $p_j$ 能被 $Q-p_1p_2\cdots p_n=1$ 整除，出现了矛盾，那么 $p_j$ 都不能整除 $Q$。这时一定存在一个不在列表中的质数，这么质数要么是 $Q$ 要么是 $Q$ 的某个质因数。这与我们假定的有有限多个质数矛盾。

注意，整个证明过程并没有证明 $Q$ 是一个质数。我们给出的是非构造性的存在证明，只是说存在某个质数不在假定的列表中。

由于质数无限多，所以给定一个整数，一定存在一个大于它的质数。现在已知的最大的质数形式是 $2^p-1$，注意这里 $p$ 是质数。这样形式的质数称为梅森素数（Mersenne primes）。卢卡斯-莱默检验法（Lucas-Lehmer test）可以快速检验这个形式的数是否是质数。不过没有其他同样快的算法能够检查其他形式的数是否是质数。

形式是 $2^n-1$ 的数不是质数。分两种情况考虑。当 $n=2k$ 时，可以分解因式 $(2^k+1)(2^k-1)$，当 $n=2k+1$ 时，也可以分解因式 $(x-1)(x^{n-1}+x^{n-2}+\cdots+1)x$。

质数有无限多，那么小于 $x$ 的质数有多少个呢？

定理 4 质数定理 当 $x$ 趋于无穷时，不超过 $x$ 的质数个数 $\pi(x)$ 与 $x/\ln x$ 趋于 1。

所有已知的证明都比较复杂。

下表给出了 $x$ 增大时，质数的个数以及与 $x/\ln x$ 的比值。

$x$	$\pi(x)$	$x∕\ln x$	$\pi(x)∕(x∕\ln x)$
103	168	144.8	1.161
104	1229	1085.7	1.132
105	9592	8685.9	1.104
106	78,498	72,382.4	1.084
107	664,579	620,420.7	1.071
108	5,761,455	5,428,681.0	1.061
109	50,847,534	48,254,942.4	1.054
1010	455,052,512	434,294,481.9	1.048

2017 年，计算到了 $$\pi(10^{26}) = 1,699,246,750,872,437,141,327,603$$ $$\pi(10^{26}) - (10^{26}∕\ln 10^{26}) = 28,883,358,936,853,188,823,261$$ 得到比例是 $1.01729$。

应用质数定理可以知道随机的选择一个数是质数的概率是多大。如果我们只选择奇数的话，概率会大一倍。

试除法可以用于质因数分解和判断一个数是否是质数，但是效率很低。最新的判定一个数是否是质数的算法只需要一个数的比特位数的多项式时间就能判定，时间复杂度是 $O((\log n)^6)$。

质因数分解仍旧没有找到多项式时间的算法。

每一个奇数在等差数列 $4k+1,4k+3,k=1,2,3,\cdots$ 其中一个。$5, 13, 17, 29, 37, 41,\cdots$ 属于 $4k+1$ 这个等差数列，$3, 7, 11, 19, 23, 31, 43,\cdots$ 属于 $4k+3$ 这个等差数列。质数有无限多，这两个等差数列上的质数也是无限多的。那么任意等差数列 $ak + b, k = 1, 2,\cdots$，其中 $a,b$ 互斥，呢？G. Lejeune Dirichlet 给出了证明，等差数列都包含无穷多的质数。其证明超过了本书的范围。不过 $3k+2,4k+3$ 这两种特殊情况比较容易证明。

证明这两个特殊情况的方式类似。反证法。假设质数有限多 $p_1,p_2,\cdots,p_n$，构造数 $3p_1p_2\cdots p_n-1$ 和 $4p_1p_2\cdots p_n-1$，类似与证明定理2 的方式，可以得出新构造的数是质数，或者包含一个非 $p_j$ 的因数是质数。

有没有一个等差数列，都是质数呢？1930 年 Paul Erdos 提出一个假设，给定任意大于 2 的整数 $n$，都有一个长度为 $n$ 的等差数列，其每个数都是质数。 Ben Green 和 Terence Tao（陶哲轩）在 2006 年给出了证明。

Conjectures and Open Problems About Primes

数论中包含很多的猜想。

是否存在一个多项式 $f(n)$ 的系数都是整数，每个 $f(n)$ 都是质数呢？每个研究这个猜想的人都会遇到 $f(n) = n^2 − n + 41$ 这个多项式，但是当 $n=41$ 时，其结果是合数。TODO 另一部分证明。See Exercise 23 in the Supplementary Exercises

哥德巴赫猜想（Goldbach's Conjecture）是数论中最著名的猜想。哥德巴赫说每一个大于 5 的奇数，都能写成三个质数之和。欧拉说这个等价于每一个大于 2 的偶数，都能写成两个质数之和。

TODO 证明 Exercise 21 in the Supplementary Exercises

截止 2018 年，计算机检查了 $4\cdot 10^{18}$ 以内的数都是正确的。陈景润在 1966 证明了一个质数和另一个数之和，后者要么是质数，要么是两个质数之积。

质数无限多个，那么形如 $n^2+1$ 的质数是不是无限多呢？Henryk Iwaniec 在 1973 给出了最接近的证明，有无限多个形如 $n^2+1$ 的数，要么是质数，要么是两个质数之积。

孪生素数猜想（The Twin Prime Conjecture）是说是否存在无数多对数 $p,p+2$ 都是质数。1966 年陈景润给出了最接近的证明，存在无限多对数，$p$ 是质数，$p+2$ 是质数或者两个质数之积。

令 $P(n)$ 表示命题存在无限多对质数对，其差值是 $n$。孪生素数猜想是 $P(2)$ 为真。数学界在尝试证明一个更弱的命题，即存在某个上界 $N$ 使得 $P(N)$ 为真。张益唐在 2013 年给出了证明，存在一个 $N<70,000,000$ 使得 $P(N)$ 为真。包括陶哲轩在内的一个数学团队，利用他的方法，将上届降到了 246，并且证明利用这个方法上届可以缩小到 6。

Greatest Common Divisors and Least Common Multiples

定义 2 令 $a, b$ 是不全为零的整数。$d$ 是满足 $d|a,d|b$ 的最大整数，称为 $a,b$ 的最大公约数，用 $\gcd(a,b)$ 表示。

两个不全为零的整数的最大公约数一定存在，因为公约数集合不为空且有限。寻找最大公约数最朴素的方法就是列出 $a,b$ 所有的因数，然后找到公共最大的一个。

定义 3 如果 $a,b$ 最大公约数是 1，那么称 $a,b$ 互斥。

定义 4 如果 $\gcd(a_i,a_j)=1,1\leq i<j\leq n$，那么 $a_1,a_2,\cdots,a_n$ 两两互斥。

另一个寻找最大公约数的方法是质数分解法。假定 $$a=p_1^{a_1}p_2^{a_2}\cdots p_n^{a_n},b=p_1^{b_1}p_2^{b_2}\cdots p_n^{b_n}$$ 其中指数是非负整数，那么 $$\gcd(a,b)=p_1^{\min(a_1,b_1)}p_2^{\min(a_2,b_2)}\cdots p_n^{\min(a_n,b_n)}$$ 为了证明其正确性，我们需要证明两个方面：这个数能整除 $a,b$ 且是所有整除 $a,b$ 中最大的。由于质因数的次数没有超过 $a,b$ 的次数，所有肯定能整除。由于任意质因数的次数增加，都无法同时被 $a,b$ 整除，所以是最大公约数。

这个方法还能用于求最小公倍数。

定义 5 $a,b$ 的最小公倍数是所有能够同时被 $a,b$ 整除的数中最小的，用 $\operatorname{lcm}(a,b)$

$a,b$ 的最小公倍数一定存在，因为公倍数集合非空，那么一定有最小值。利用质因数分解法可以得到最小公倍数 $$\operatorname{lcm}(a,b)=p_1^{\max(a_1,b_1)}p_2^{\max(a_2,b_2)}\cdots p_n^{\max(a_n,b_n)}$$ 证明和最大公约数类似，明显地，这个数可以同时被 $a,b$ 整除，同时如果质因数幂次较少一次，则无法被 $a$ 或者 $b$ 整除。

最小公倍数和最大公约数有如下关系：

定理 5 令 $a,b$ 是正整数，那么 $$ab=\gcd(a,b)\cdot\operatorname{lcm}(a,b)$$

证明：通过质因数分解法证明。不是一般性，我们考察 $p_i$ 的指数。不妨设 $a_i\geq b_i$，那么 $\max(a_i,b_i)=a_i,\min(a_i,b_i)=b_i$，$ab$ 的 $p_i$ 的次数是 $a_ib_i$。$\gcd(a,b)$ 的 $p_i$ 的次数是 $\min(a_i,b_i)=b_i$，类似的 $\operatorname{lcm}(a,b)$ 的 $p_i$ 次数是 $a_i$，对应幂次相等。

The Euclidean Algorithm

分解质因数法非常低效，因为分解质因数本身没有高效的算法。欧几里得就发明了辗转相除法，高效地求最大公约数。

引理 1 令 $a=bq+r$，其中 $a,b,q,r$ 都是整数。那么 $\gcd(a,b)=\gcd(b,r)$。

证明：如果能证明 $a,b$ 和 $b,r$ 的公约数相同，那么必然最大公约数也相同。

假设 $d$ 能整除 $a,b$，那么根据 4.1 节定理 1，得到 $d$ 能整除 $a-bq=r$，因此 $a,b$ 的公约数也是 $b,r$ 的公约数。

假设 $d$ 能整除 $b,r$，那么 $d$ 能整除 $bq+r=a$，因此 $b,r$ 的公约数也是 $a,b$ 的公约数。

下面是欧几里得算法的描述，5.3 节会给出证明，该算法的时间复杂度是 $O(\log b)$，前提是假定 $a\geq b$。

procedure - gcd(a, b: positive integers)
x := a
y := b
while y != 0
    r := x mod y
    x := y
    y := r
return x

gcds as Linear Combinations

定理 6 裴蜀定理（Bezout） 如果 $a,b$ 是正整数，那么存在整数 $s,t$ 使得 $\gcd(a,b)=sa+tb$。

也就是说，$\gcd(a,b)$ 可以表示为 $a,b$的 整系数的线性组合。

定义 6 $a,b$ 是正整数，使得 $\gcd(a,b)=sa+tb$ 成立的整数 $s,t$ 称为裴蜀系数，这个等式称为裴蜀等式。

TODO Exercise 36 in Section 5.2 and [Ro10] for proof

这里介绍两个求解的方法。第一个需要正向应用一遍欧几里得算法，然后反向处理一遍，具体参考下面的例子。第二个方法只需要正向一遍，被称为扩展欧几里得算法（extended Euclidean algorithm）。

扩展欧几里得算法初始时令 $s_0=1,s_1=0,t_0=0,t_1=1$，迭代公式是 $$s_j = s_{j−2} − q_{j−1}s_{j−1}, t_j = t_{j−2} − q_{j−1}t_{j−1}$$ 其中 $j=2,3,4,\cdots,n$，$q_j$ 是欧几里得算法中每一步的商。

TODO see Exercise 44 in Section 5.2, or see [Ro10]

例 使用第一种方法将 $\gcd(252,198)=18$ 表示成 252 和 198 的线性组合。

首先使用欧几里得算法计算最大公约数。 $$\begin{aligned} 252 &= 198 \cdot 1 + 54\\ 198 &= 54 \cdot 3 + 36\\ 54 &= 36 \cdot 1 + 18\\ 36 &= 18 \cdot 2 + 0 \end{aligned}$$

使用表格总结这个过程就是 | $j$ | $r_j$ | $r_{j+1}$ | $q_{j+1}$ | $r_{j+2}$ | |--|--|--|--|--| | $0$ | $252$ | $198$ | $1$ | $54$ | | $1$ | $198$ | $54$ | $3$ | $36$ | | $2$ | $54$ | $36$ | $1$ | $18$ | | $3$ | $36$ | $18$ | $2$ | $0$ |

然后从倒数第二个式子开始倒着处理。可以将 $\gcd(252,198)=18$ 表示为 $$18=54-36\cdot 1$$ 下一行告诉我们 $$36=198-54\cdot 3$$ 带入第一个式子得到 $$18=54-(198-54\cdot 3)\cdot 1=54\cdot 4-198$$ 上表第一个式子告诉我们 $$54=252-198$$ 代入之前的式子 $$18=(252-198)\cdot 4-198=252\cdot 4-198\cdot 5$$

例 使用扩展欧几里得算法将 $\gcd(252,198)=18$ 表示成 252 和 198 的线性组合。

解：从上个例子可知，计算 $\gcd(252,198)=18$ 时每次的商是 $q_1 = 1, q_2 = 3, q_3 = 1, q_4 = 2$，这里不再计算。令 $s_0 = 1, s_1 = 0, t_0 = 0, t_1 = 1$，应用 $$s_j = s_{j−2} − q_{j−1}s_{j−1}, t_j = t_{j−2} − q_{j−1}t_{j−1}$$ 进行迭代。 $$s_2 = s_0 − s_1q_1 = 1 − 0 \cdot 1 = 1, t_2 = t_0 − t_1q_1 = 0 − 1 \cdot 1 = −1$$ $$s_3 = s_1 − s_2q_2 = 0 − 1 \cdot 3 = −3, t_3 = t_1 − t_2q_2 = 1 − (−1)3 = 4$$ $$s_4 = s_2 − s_3q_3 = 1 − (−3) \cdot 1 = 4, t_4 = t_2 − t_3q_3 = −1 − 4 \cdot 1 = −5$$ 所以 $$\gcd(252,198)=18=4\cdot 252-198\cdot 5$$ 扩展欧几里得算法的计算过程可以总结为下表：

$j$	$r_j$	$r_{j+1}$	$q_{j+1}$	$r_{j+2}$	$s_j$	$t_j$
0	252	198	1	54	1	0
1	198	54	3	36	0	1
2	54	36	1	18	1	−1
3	36	18	2	0	−3	4
4					4	−5

使用定理 6 可以部分证明算术基本定理，一个合数能做质因数分解，那么按照非递减序排列，结果是唯一的。

引理 2 如果 $a,b,c$ 是正整数，并且 $\gcd(a,b)=1,a|bc$，那么 $a|c$。

证明：因为 $\gcd(a,b)=1$，根据 定理 6 有 $$sa+tb=1$$ 两边同时乘以 $c$ $$sac+tbc=c$$ 根据 4.1 小节的定理一，由 $a|bc$ 得到 $a|tbc$。显然 $a|tac$，所有 $a|(sac+tbc)$。所以 $a|c$。

下面的引理是上面引理的泛化形式。

引理 3 如果 $p$ 是质数且 $p|a_1a_2\cdots a_n$，其中 $a_i$ 是整数，那么对于某些 $i$ 有 $p|a_i$。

TODO The proof of Lemma 3 is left as Exercise 64 in Section 5.1

下面证明算术基本定理的唯一性。

证明（算术基本定理的唯一性）：反证法。假定有至少两种不同的质因数分解方式：$n = p_1p_2 \cdots p_s=q_1q_2 \cdots q_t$，其中 $p_i,q_j$ 是质数且 $p_1\leq p_2\leq\cdots\leq p_s,q_1\leq q_2\leq\cdots\leq q_t$。消除相同的质数后 $$p_{i_1}p_{i_2} \cdots p_{i_u} = q_{j_1}q_{j_2} \cdots q_{j_v}$$ 其中 $u,v$ 是正整数。两边没有相同的质数了。根据引理 2，一定存在某个 $k$ 使得 $p_{i_1}$ 能够 $q_{j_k}$ 整除，但是两个质数不可能有整除关系，矛盾。所以质因数分解是唯一的。

4.1 节定理 5 是说两边同乘一个数，同余性质不变，但是不能随便同除一个数，不过可以同除一个与模数互质的数。

定理 7 令 $m$ 是正整数，$a,b,c$ 是整数。如果 $ac\equiv bc(\operatorname{mod} m)$，且 $\gcd(c,m)$，那么 $a\equiv b(\operatorname{mod} m)$。

证明：由 $ac\equiv bc(\operatorname{mod} m)$ 得到 $m|(ac-bc)=c(a-b)$，根据引理 2 得到 $m|(a-b)$，所以 $a\equiv b(\operatorname{mod} m)$。