第六章 费马定理与二次剩余

---

1、Fermat's theorem(费马定理)

本章我们将应用上一张的知识证明一系列经典定理，这些定理主要源于 Fermat(费马),Euler(欧拉),Legendre(勒让德),Gauss(高斯)

Theorem 70
如果 $p$ 是素数，那么
$a^p\equiv a \pmod p$

根据 Theorem 55，可以推导出

Theorem 71（费马定理）
如果 $p$ 是素数，且 $p\nmid a$，那么
$a^{p-1}\equiv 1 \pmod p$

更一般的定理如下：

Theorem 72（欧拉定理）
如果 $(a,m)=1$，那么
$a^{\phi(m)}\equiv 1\pmod m$

如果 $x$ 取遍模 $m$ 的简化剩余系，那么根据 Theorem 58，$ax$ 也取遍模 $m$ 的简化剩余系，因此

$\prod(a x) \equiv \prod x(\bmod m)$

$a^{\phi(m)} \prod x \equiv \prod x(\bmod m)$

由于 $x$ 属于简化剩余系，所以 $(x,m)=1$，因此

$a^{\phi(m)}\equiv 1\pmod m$

---

2、Some properties of binomial coefficients(二项式系数的性质)

关于欧拉定理，欧拉本人给出的证明并非如此，它依赖于二项式系数的性质

Theorem 73
如果 $m,n$ 是正整数，那么二项式系数
$\binom{m}{n}=\frac{m(m-1) \ldots(m-n+1)}{n !}\\ \binom{-m}{n}=(-1)^{n} \frac{m(m+1) \ldots(m+n-1)}{n !}$
是整数

由于

$\binom{-m}{n}=(-1)^{n}\binom{m+n-1}{n}$

所以定理的两部分是等价的，每一部分都有一种更为优秀的表达

Theorem 74
任意 $n$ 个连续正整数的乘积都能被 $n!$ 整除

我们用二维形式的数学归纳法证明这个定理，记上升幂

$(m)_{n}=m(m+1) \ldots(m+n-1)$

那么定理内容即 $n!|(m)_{n}$

当 $n=1$ 时，定理显然对所有的 $m$ 成立

当 $m=1$ 时，定理显然对所有的 $n$ 成立

假设当 $n=N-1$ 时定理对所有的 $m$ 成立，且当 $n=N,m=M$ 时定理成立，那么

$(M+1)_{N}-M_{N}=N(M+1)_{N-1}$

由于 $(N-1)!|(M+1)_{N-1}$，因此 $N!|(M+1)_{N}$

即我们推导出了定理对于 $n=N,m=M+1$ 成立，证毕

Theorem 75
如果 $p$ 是素数，那么
$\binom{p}{1},\binom{p}{2},\cdots,\binom{p}{p-1}$
能被 $p$ 整除

对于 $1\leq n\leq p-1$

$\binom{p}{n}=p \frac{(p-1)(p-2) \ldots(p-n+1)}{n !}$

根据 Theorem 74，有

$n ! | p(p-1) \ldots(p-n+1)$

而 $(n!,p)=1$，因此

$n ! | (p-1) \ldots(p-n+1)$

故 $\binom{p}{n}$ 能被 $p$ 整除

Theorem 76
若 $p$ 是素数，那么 $(1-x)^{-p}$ 展开式的各项系数中
（1）$x^{0},x^{p},x^{2p},\cdots$ 项系数与 $1$ 同余 $\pmod p$
（2）其余项系数被 $p$ 整除

$(1-x)^{-p}=1+\sum_{n=1}^{\infty}\binom{p+n-1}{n}x^{n}$

（1）由 Lucas(卢卡斯) 定理，第 $x^{kp}$ 项系数

$\binom{p+kp-1}{kp}\equiv\binom{p-1}{0}\binom{k}{k}\equiv 1\pmod p$

注：我们后面会讲到如下的卢卡斯定理

Theorem by Lucas
若 $p$ 是素数，那么
$\binom{n}{m}\equiv\binom{n\%p}{m\%p}\binom{\left\lfloor n/p\right\rfloor}{\left\lfloor m/p \right\rfloor}\pmod p$

（2）我们知道

$\left(1-x^{p}\right)^{-1}=1+x^{p}+x^{2 p}+\ldots$

每项系数都是整数，因此

$\left(1-x^{p}\right)^{-1}-(1-x)^{-p}=(1-x)^{-p}\left(1-x^{p}\right)^{-1}[(1-x)^{p}-1+x^{p}]$

左边的展开式中每项都是整数，而右边的式子中

$(1-x)^{p}-1+x^{p}=\sum_{r=1}^{p-1}(-1)^{r}\left(\begin{array}{l}{p} \\ {r}\end{array}\right) x^{r}$

根据 Theorem 75，每项系数都能被 $p$ 整除，证毕

Theorem 77
若 $p$ 是素数，那么
$(x+y+\cdots+w)^{p} \equiv x^{p}+y^{p}+\cdots+w^{p}\pmod p$

由 Theorem 75 容易看出

$(x+y)^{p} \equiv x^{p}+y^{p} \pmod p$

因此

$(x+y+z)^{p}=\sum_{r=0}^{p}\binom{p}{r}(x+y)^{r}z^{p-r}\equiv x^p+y^p+z^p\pmod p$

这样重复下去，就能得到 $n$ 项的结果

Theorem 78
若 $\alpha>0$，那么
$m \equiv 1\left(\bmod p^{\alpha}\right)\Rightarrow m^{p} \equiv 1\left(\bmod p^{\alpha+1}\right)$

由式子可得

$m \equiv 1\left(\bmod p^{\alpha}\right)\Rightarrow m=kp^{\alpha}+1$

其中 $k\in Z$，又有 $\alpha p\geq \alpha +1$，因此

$m^{p}=\left(1+k p^{\alpha}\right)^{p}=1+l p^{\alpha+1}\equiv 1\pmod{p^{\alpha+1}}$

---

3、The second proof of Theorem 72

我们现在介绍欧拉本人对 Theorem 72 的证明

设 $m=\Pi p^{\alpha}$，那么根据 Theorem 53，我们只需要证明

$a^{\phi(m)} \equiv 1\left(\bmod p^{\alpha}\right)$

我们知道

$\phi(m)=\prod \phi\left(p^{\alpha}\right)=\prod p^{\alpha-1}(p-1)$

因此我们只需要证明

$a^{p^{\alpha-1}(p-1)} \equiv 1\left(\bmod p^{\alpha}\right)$

根据 Theorem 77

$(x+y+\ldots)^{p} \equiv x^{p}+y^{p}+\ldots(\bmod p)$

令 $x=y=z=\cdots=1$，设共有 $a$ 个数，那么

$a^{p} \equiv a\Rightarrow a^{p-1}\equiv 1\pmod p$

根据 Theorem 78

$a^{p(p-1)} \equiv 1\left(\bmod p^{2}\right)$

$a^{p^{2}(p-1)} \equiv 1\left(\bmod p^{3}\right)$

$\cdots\cdots$

$a^{p^{\alpha-1}(p-1)} \equiv 1\left(\bmod p^{\alpha}\right)$

---

4、Proof of Theorem 22

在研究费马定理更广泛的应用之前，我们先来填个坑，证明 Theorem 22

我们把 $f(n)$ 写出下面的形式

$f(n)=\sum_{r=1}^{m} Q_{r}(n) a_{r}^{n}=\sum_{r=1}^{m}\left(\sum_{s=0}^{q_{r}} c_{r, s}n^s\right) a_{r}^{n}$

其中 $\{a\},\{c\}$ 是整数列，且满足

$1 \leqslant a_{1}<a_{2}<\ldots<a_{m}$

也就是说把 $f(n)$ 的项按照对函数值的影响排序，因此，对于足够大的 $n$，要保证函数值为正，需要最后一项的系数

$a_m,c_{m,q_{m}}>0$

假设对于足够大的 $n$，$f(n)$ 都是素数，那么存在一个 $n$ 满足

$f(n)=p>a_{m}$

我们知道对于任意的 $k,s$ 有

$\{n+k p(p-1)\}^s \equiv n^{s}(\bmod p)$

且根据欧拉定理有

$a_{r}^{n+K(p-1)} \equiv a_{r}^{n}(\bmod p)$

因此对于任意的正整数 $k$ 有

$\{n+k p(p-1)\}^{s} a_{r}^{n+k p(p-1)} \equiv n^{s} a_{r}^{n}(\bmod p)$

因此

$f\{n+k p(p-1)\} \equiv f(n) \equiv 0(\bmod p)$

得出矛盾，证毕

---

5、Quadratic residues(二次剩余)

设 $p$ 是奇素数且 $p\nmid a$，$x$ 是下列数中的一个

$1,2,3, \ldots, p-1$

那么根据 Theorem 58，下列数中仅有一个与 $a$ 同余 $\pmod p$

$x,2x,3x,\cdots,(p-1)x$

因此有唯一的 $x'$ 满足

$x x^{\prime} \equiv a(\bmod p), \quad 0<x^{\prime}<p$

我们称 $x,x'$ associate(数论共轭)

注：原文是这样写的

We call x' the associate of x

我觉得它们的关系有点像共轭，就起了个数论共轭的名字，也有人翻译为伴随

那么当 $x$ 与自身数论共轭时，就有两种可能：

（1）与自身数论共轭的 $x_1$ 存在，即同余方程

$x^2\equiv a(\bmod p)$

有解 $x=x_1$，我们称 $a$ 是模 $p$ 的一个 quadratic residue(二次剩余)，记作

$a \mathbf{R} p$

容易看出

$x_2=p-x_1=-x_1(\bmod p)$

是这个同余方程的另一个解，反过来，如果 $x_1,x_2$ 是方程的解，那么

$x_{1}^{2} \equiv a, x_{2}^{2} \equiv a \Rightarrow\left(x_{1}-x_{2}\right)\left(x_{1}+x_{2}\right)=x_{1}^{2}-x_{2}^{2} \equiv 0(\bmod p)$

因此同余方程仅有两个解，分别为 $x_1,p-x_1$

现在，模 $p$ 的完全剩余系

$1,2,\cdots,p-1$

可以分成三个部分：$x_1,p-x_1$，以及上下的 $\frac{1}{2}(p-3)$ 对互为数论共轭的数，而

$x_{1}\left(p-x_{1}\right) \equiv-x_{1}^{2} \equiv-a(\bmod p)$

$x x^{\prime} \equiv a(\bmod p)$

因此

$(p-1) !=\prod x \equiv-a \cdot a^{\frac{1}{2}(p-3)} \equiv-a^{\frac{1}{2}(p-1)}(\bmod p)$

（2）与自身数论共轭的 $x_1$ 不存在，即同余方程

$x^2\equiv a(\bmod p)$

无解，我们称 $a$ 是模 $p$ 的一个 quadratic non-residue(二次非剩余)，记作

$a \mathbf{N} p$

这种情况下，模 $p$ 的完全剩余系

$1,2,\cdots,p-1$

可以分成 $\frac{1}{2}(p-1)$ 对互为数论共轭的数，因此

$(p-1) !=\prod x \equiv a^{\frac{1}{2}(p-1)}(\bmod p)$

现在我们就可以定义 Legendre's symbol(勒让德符号) 为

$\left(\frac{a}{p}\right) \triangleq\left\{\begin{array}{l}{+1, \quad \text { if } \quad a \mathbf{R} p} \\ {-1, \quad \text { if } \quad a \mathbf{N} p}\end{array}\right.$

从定义可以看出，如果 $a \equiv b(\bmod p)$，那么

$\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$

并且容易得到下面的定理：

Theorem 79
若 $p$ 是奇素数且 $(a,p)=1$，那么
$(p-1) ! \equiv-\left(\frac{a}{p}\right) a^{\frac{1}{2}(p-1)}(\bmod p)$

在上面的讨论中，我们都有一个 $p$ 是奇数的条件，这是因为 $0,1$ 都是模 $2$ 的二次剩余，因此当 $p=2$ 时，我们没有定义勒让德符号，并且在接下来的研究中，我们都要忽略这一情况。

值得一提的是，当 $p=2$ 时某些定理是成立的，但是也有一些定理不成立。

---

6、Wilson's theorem(威尔逊定理)

我们知道，同余方程

$x^2\equiv 1(\bmod p)$

有解 $x=\pm 1$，因此 $1$ 是模 $p$ 的二次剩余，

$\left(\frac{1}{p}\right)=1$

那么在 Theorem 79 中，我们令 $a=1$ 就得到了

Theorem 80(威尔逊定理)
若 $p$ 是素数，则
$(p-1)!\equiv -1(\bmod p)$

根据这个定理，我们能得到许多结论，比如 $11|3628801$

值得一提的是，同余式

$(p-1)!\equiv -1(\bmod p^2)$

仅当 $p=5,13,563$ 时成立（在小于 $200000$ 的范围内），目前还没有关于这个同余式的一般性结论

我们考虑威尔逊定理的否命题，如果 $m$ 是合数，那么

$m |(m-1) !+1$

不可能成立，因为 $m$ 有一个因子 $d$ 满足 $1<d<m$，因此有

Theorem 81
若 $m>1$，那么 $m$ 是素数的一个充要条件是
$m |(m-1) !+1$

这个定理在素数测试中不怎么有用，因为阶乘实在是太难算了

根据威尔逊定理，我们可以得到

$\left(\frac{-1}{p}\right) \equiv-(-1)^{\frac{1}{2}(p-1)}(p-1) ! \equiv(-1)^{\frac{1}{2}(p-1)}$

因此有如下定理：

Theorem 82
对于 $4k+1$ 型素数 $p$，$-1$ 是模 $p$ 的二次剩余
对于 $4k+3$ 型素数 $p$，$-1$ 是模 $p$ 的二次非剩余

更一般的，有

Theorem 83
$\left(\frac{a}{p}\right) \equiv a^{\frac{1}{2}(p-1)}(\bmod p)$

---

7、Elementary properties of quadratic residues and non-residues(二次剩余与二次非剩余的性质)

下面的数

$1^{2}, 2^{2}, 3^{2}, \ldots,\left\{\frac{1}{2}(p-1)\right\}^{2}$

两两不同余，因为 $r^2\equiv s^2\Rightarrow r\equiv\pm s\pmod p$，这是不可能的

我们知道

$r^{2} \equiv(p-r)^{2}(\bmod p)$

因此，我们有下面的定理

Theorem 84
关于模奇素数 $p$，有 $\frac{1}{2}(p-1)$ 个二次剩余和 $\frac{1}{2}(p-1)$ 个二次非剩余

接下来我们研究一个比较神奇的定理

Theorem 85
两个二次剩余或两个二次非剩余的乘积是二次剩余
一个二次剩余和一个二次非剩余的乘积是二次非剩余

这个定理的描述等价于

$\left(\frac{a b}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$

而事实上，由 Theorem 83 可知

$\left(\frac{a b}{p}\right)=(ab)^{\frac{1}{2}(p-1)}=a^{\frac{1}{2}(p-1)}b^{\frac{1}{2}(p-1)}=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$

接下来的两个定理将在第二十章用到

Theorem 86
若 $p$ 是 $4k+1$ 型素数，那么存在一个 $x$ 使得
$1+x^2=mp$
其中 $0<m<p$

根据 Theorem 82，方程

$x^2+1\equiv 0(\bmod p)$

有解，且 $x\leq \frac{1}{2}(p-1)$，因此

$0<1+x^2<1+(\frac{1}{2}p)^2<p^2$

Theorem 87
若 $p$ 是奇素数，那么存在整数 $x,y$ 满足
$1+x^2+y^2=mp$
其中 $0<m<p$

考虑下面的 $\frac{1}{2}(p+1)$ 个数

$x^{2}\left(0 \leqslant x \leqslant \frac{1}{2}(p-1)\right)$

它们两两不同余，下面的 $\frac{1}{2}(p+1)$ 个数也是两两不同余

$-1-y^{2}\left(0 \leqslant y \leqslant \frac{1}{2}(p-1)\right)$

它们合在一起共有 $p+1$ 个数，说明必定存在两个数同余，即

$x^2\equiv-1-y^2(\bmod p)$

且 $x,y<\frac{p}{2}$，故

$0<1+x^{2}+y^{2}<1+2\left(\frac{1}{2} p\right)^{2}<p^{2}$

结合 Theorem 86 可知，当 $p=4k+1$ 时，可以取 $y=0$

---

8、The order and the primitive root(阶和原根)

我们知道，根据 Theorem 72，当 $(a,m)=1$ 时，

$a^{\phi(m)}\equiv 1(\bmod m)$

我们设 $d$ 是下面同余方程的最小正整数解：

$a^{x}\equiv 1(\bmod m)$

那么显然有 $d\leq \phi(m)$，我们称 $d$ 是 $a$ 的 order(阶) 或 a belongs to d $\pmod m$

例如，我们知道

$2 \equiv 2, \quad 2^{2} \equiv 4, \quad 2^{3} \equiv 1(\bmod 7)$

因此 $3$ 是 $2$ 的阶，或 $2$ belongs to $3$ $\pmod 7$

特别的，如果 $d=\phi(m)$，我们称 $a$ 是模 $m$ 的 primitive root(原根)

例如，我们知道

$2 \equiv 2, \quad 2^{2} \equiv 4, \quad 2^{3} \equiv 3, \quad 2^{4} \equiv 1(\bmod 5)$

因此 $2$ 是模 $5$ 的原根，同样的，$3$ 是模 $17$ 的原根

记上面的同余方程 $a^{x}\equiv 1(\bmod m)$ 为命题 $P(x)$，那么显然

$P(x),P(y)\rightarrow P(x+y)$

且当 $y\leq x$ 时，

$a^{x-y}\equiv b\Rightarrow a^{x}\equiv ba^{y}\Rightarrow b\equiv 1\pmod m$

因此

$P(x),P(y)\rightarrow P(x-y)$

因此，根据 Theorem 69，

$d|\phi(m)$

我们发现，对于原根的理解和代数学中单位根的理解是类似的（FFT$\rightarrow$NTT），我们将在下一章证明所有的奇素数都存在原根

现在我们可以总结一下我们刚才证明的东西

Theorem 88
（1）$a$ 模 $m$ 的阶 $d$ 一定是 $\phi(m)$的因子，即
$d|\phi(m)$
（2）若 $m$ 是素数 $p$，那么 $d|(p-1)$
（3）同余式 $a^{x}\equiv 1(\bmod m)$ 成立当且仅当 $x$ 是 $d$ 的倍数

---

9、The converse of Fermat's theorem(费马逆定理)

费马定理的逆定理是不正确的，即

若 $(a,m)=1$ 且 $a^{m-1}\equiv 1(\bmod m)$，则 $m$ 不一定是素数

例如，取 $m=561=3\times 11\times 17$，且 $(a,561)=1$，则

$a^{2} \equiv 1(\bmod 3), \quad a^{10} \equiv 1(\bmod 11), \quad a^{16} \equiv 1(\bmod 17)$

我们知道 $2|560,10| 560,16 | 560$，因此

$a^{560} \equiv 1(\bmod 3),\quad a^{560} \equiv 1(\bmod 11),\quad a^{560} \equiv 1(\bmod 17)$

故 $a^{560}\equiv 1(\bmod 561)$，这样我们就找到了一个反例

如果对于特定的 $a$（$a,m$互素），合数 $m$ 满足费马定理，称这样的合数为 pseudo-prime(伪素数)

如果对于任意的 $a$（$a,m$互素），合数 $m$ 满足费马定理，称这样的合数为 Carmichael number(卡迈尔数)

显然，卡迈尔数一定是伪素数

目前尚未证明是否存在无穷多个卡迈尔数，甚至尚未证明是否存在无穷多个合数 $m$ 满足 $2^{m}\equiv 2(\bmod m)$ 或 $3^{m}\equiv 3(\bmod m)$

但是我们已经证明了下面的定理

Theorem 89
对于任意的 $a>1$（$a,m$互素），存在无穷多个伪素数满足费马定理

设 $p$ 是奇素数且不被 $a(a^2-1)$ 整除，我们取

$m=\frac{a^{2 p}-1}{a^{2}-1}=\left(\frac{a^{p}-1}{a-1}\right)\left(\frac{a^{p}+1}{a+1}\right)$

显然 $m$ 是合数，且有

$\left(a^{2}-1\right)(m-1)=a^{2 p}-a^{2}=(a^p-a)(a^p+a)=a\left(a^{p-1}-1\right)\left(a^{p}+a\right)$

由于 $a$ 和 $a^p$ 奇偶性相同，故 $2|(a+a^p)$

根据费马定理，$p|(a^{p-1}-1)$

由于 $p-1$ 是偶数，故 $(a^2-1)|(a^{p-1}-1)$

而 $(p,a^2-1)=1$，故 $2 p\left(a^{2}-1\right) |\left(a^{2}-1\right)(m-1)$

因此 $2p|(m-1)$，不妨设 $m=2pk+1$，则

$a^{2p}=(a^2-1)(m-1)+a^2=1+m(a^2-1)\equiv 1(\bmod m)$

因此

$a^{m-1}=a^{2pk}\equiv 1(\bmod m)$

因此只要取一个奇素数 $p$，我们就能确定一个满足费马定理的合数 $m$，证毕

注：在上面的证明过程中，$a>1$ 保证了 $m$ 的合法性

Theorem 90
若 $(a,m)=1$，且满足
（1）$a^{m-1}\equiv 1 (\bmod m)$
（2）$a^{x}\not\equiv 1 (\bmod m)$，其中 $x|(m-1)$ 且 $x\neq m-1$
则 $m$ 是素数

设 $d$ 是 $a$ 的阶 $(\bmod m)$，根据 Theorem 88，

$d|(m-1),\quad d|\phi(m)$

由于 $a^d\equiv 1(\bmod m)$，再加上本定理条件，有

$d=m-1,\quad (m-1)|\phi(m)$

假设 $m$ 是合数，则有

$\phi(m)=m \prod_{p | m}\left(1-\frac{1}{p}\right)<m-1$

得到矛盾，因此 $m$ 是素数

---

10、Divisibility of $2^{p-1}-1$ by $p^2$

根据费马定理，我们知道

$2^{p-1}-1 \equiv 0(\bmod p)$

那么当 $p>2$ 时，下面的同余式是否成立呢？

$2^{p-1}-1 \equiv 0(\bmod p^{2})$

这个问题对于解决著名的 Fermat's last theorem(费马最终定理) 非常重要

事实上，这个式子确实有可能成立，但是对应的 $p$ 非常稀少

Theorem 91
存在素数 $p$ 满足
$2^{p-1}-1 \equiv 0\left(\bmod p^{2}\right)$

事实上，当 $p=1093$ 时成立，我们可以通过简单的计算进行验证

这里我们给出一个简短的证明，当 $p=1093$ 时，$p^2=1194649$

$3^{7}=2187=2 p+1, \quad 3^{14}=(2 p+1)^{2} \equiv 4 p+1(\bmod p^{2})$

$2^{14}=16384=15 p-11, \quad 2^{28} \equiv-330 p+121(\bmod p^{2})$

$3^{2} \times 2^{28} \equiv-2970 p+1089=-2969 p-4 \equiv-1876 p-4(\bmod p^{2})$

因此

$3^{2} \times 2^{26} \equiv-469 p-1(\bmod p^{2})$

根据二项式定理

$3^{14} \times 2^{182} \equiv-(469 p+1)^{7} \equiv-3283 p-1 \equiv-4 p-1 \equiv-3^{14}(\bmod p^{2})$

$2^{182} \equiv-1, \quad 2^{1092} \equiv 1\left(\bmod 1093^{2}\right)$

当 $p=3511$ 时也是成立的，事实上，在 $p<3\times 10^7$ 范围内只有这两个素数成立

---

11、Gauss's Lemma(高斯引理)

设 $p$ 是奇素数，那么 $[-\frac{p}{2},\frac{p}{2}]$ 之间的所有整数构成了一个完全剩余系，我们把落在这个区间的数称为模 $p$ 的 minimal residue(极小剩余)

我们可以看出，极小剩余的正负由落在区间 $[0,\frac{p}{2}]$ 还是 $[\frac{p}{2},p-1]$ 决定

现在设 $m$ 是与 $p$ 互素的整数，考虑下面这 $\frac{1}{2}(p-1)$ 个数

$m, 2 m, 3 m, \ldots, \frac{1}{2}(p-1) m$

我们可以按照模 $p$ 的极小剩余的正负将它们划分为

$r_{1}, r_{2}, \ldots, r_{\lambda}, \quad-r_{1}^{\prime},-r_{2}^{\prime}, \ldots,-r_{\mu}^{\prime}$

其中

$\lambda+\mu=\frac{1}{2}(p-1), \quad 0<r_{i}<\frac{1}{2} p, \quad 0<r_{i}^{\prime}<\frac{1}{2} p$

显然，$r$ 两两不同余，且 $r^{\prime}$ 两两不同余

假设存在一对 $r_i=r^{\prime}_j$，其中

$a m \equiv r_{i}, \quad b m \equiv-r_{j}^{\prime} \pmod p$

则

$am+bm\equiv 0\Rightarrow a+b\equiv 0\pmod p$

但是 $0<a,b<\frac{1}{2}(p-1)$，这是不可能的

因此，所有的 $r$ 和 $r^{\prime}$ 两两不同余，它们是 $1,2, \ldots, \frac{1}{2}(p-1)$ 的一个排列

故有

$m \times 2 m \times\cdots\times \frac{1}{2}(p-1) m \equiv(-1)^{\mu} 1\times 2 \times\cdots\times \frac{1}{2}(p-1)(\bmod p)$

$m^{\frac{1}{2}(p-1)}\equiv (-1)^{\mu}(\bmod p)$

根据 Theorem 83，我们知道

$\left(\frac{m}{p}\right) \equiv m^{\frac{1}{2}(p-1)}(\bmod p)$

这样我们就得到了著名的高斯引理

Theorem 92（高斯引理）
$\left(\frac{m}{p}\right)=(-1)^{\mu}$
其中，$\mu$ 是下列数
$m, 2 m, 3 m, \ldots, \frac{1}{2}(p-1) m$
中最小非负剩余 $(\bmod p)$ 大于 $\frac{1}{2}p$ 的数的个数

高斯引理可以用来判断 $m$ 是否为模 $p$ 的二次剩余，例如，取 $m=2$，得到对应的

$2,4, \ldots, p-1$

接下来引入一个常用的记号 $[x]$ 表示 $x$ 的整数部分，即

$x=[x]+f$

其中 $0\leq f<1$，例如

$\left[\frac{5}{2}\right]=2, \quad\left[\frac{1}{2}\right]=0, \quad\left[-\frac{3}{2}\right]=-2$

有了这个记号，我们就可以写出

$\lambda=\left[\frac{1}{4}p\right]$

$\mu=\frac{1}{2}(p-1)-\left[\frac{1}{4} p\right]$

若 $p \equiv 1(\bmod 4)$，那么

$\mu=\frac{1}{2}(p-1)-\frac{1}{4}(p-1)=\frac{1}{4}(p-1)=\left[\frac{1}{4}(p+1)\right]$

若 $p \equiv 3(\bmod 4)$，那么

$\mu=\frac{1}{2}(p-1)-\frac{1}{4}(p-3)=\frac{1}{4}(p+1)=\left[\frac{1}{4}(p+1)\right]$

因此，根据高斯引理

$\left(\frac{2}{p}\right) \equiv 2^{\frac{1}{2}(p-1)} \equiv(-1)^{\left[\frac{1}{4}(p+1)\right]} (\bmod p)$

若 $p=8n\pm 1$，则 $\left(\frac{2}{p}\right)=1$，同时 $\frac{1}{8}\left(p^{2}-1\right)$ 是偶数

若 $p=8n\pm 3$，则 $\left(\frac{2}{p}\right)=-1$，同时 $\frac{1}{8}\left(p^{2}-1\right)$ 是奇数

至此，又发现原书的一个错误，截图留念

总结一下，得到下面的定理

Theorem 93
$\left(\frac{2}{p}\right)=(-1)^{\left[\frac{1}{4}(p+1)\right]}$

Theorem 94
$\left(\frac{2}{p}\right)=(-1)^{\left[\frac{1}{8}\left(p^{2}-1\right)\right]}$

Theroem 95
若 $p$ 是 $8n\pm 1$ 型素数，则 $2$ 是模 $p$ 的二次剩余
若 $p$ 是 $8n\pm 3$ 型素数，则 $2$ 是模 $p$ 的二次非剩余

再来看一个例子，取 $m=-3$，得到序列

$-3 a \quad\left(1 \leqslant a<\frac{1}{2} p\right)$

接下来考虑 $\mu$ 的计算

若 $1\leq a<\frac{1}{6}p$，则 $\frac{1}{2}p<p-3a<p$，$-3a$ 的剩余落在 $[\frac{1}{2}p,p-1]$ 之间

若 $\frac{1}{6}p<a<\frac{1}{3}p$，则 $0<p-3a<\frac{1}{2}p$，$-3a$ 的剩余落在 $[0,\frac{1}{2}p]$ 之间

若 $\frac{1}{3}p<a<\frac{1}{2}p$，则 $\frac{1}{2}p<2p-3a<p$，$-3a$ 的剩余落在 $[\frac{1}{2}p,p-1]$ 之间

注：这里我们设 $p>3$，故分类讨论中 $a\neq \frac{1}{6}p,\frac{1}{3}p$

因此

$\mu=\left[\frac{1}{6} p\right]+\left[\frac{1}{2} p\right]-\left[\frac{1}{3} p\right]$

Theorem 96
若 $p$ 是 $6n+1$ 型素数，则 $-3$ 是模 $p$ 的二次剩余
若 $p$ 是 $6n+5$ 型素数，则 $-3$ 是模 $p$ 的二次非剩余

结合下一节要讲的二次互反律，我们可以得到更深的结果

Theorem 97
若 $p$ 是 $10n\pm 1$ 型素数，则 $5$ 是模 $p$ 的二次剩余
若 $p$ 是 $10n\pm 3$ 型素数，则 $5$ 是模 $p$ 的二次非剩余

---

12、The law of reciprocity(二次互反律)

二次剩余领域最著名的定理莫属高斯的二次互反律，即

Theorem 98
若 $p,q$ 是奇素数，那么
$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{p^{\prime} q^{\prime}}$
其中
$p^{\prime}=\frac{1}{2}(p-1), \quad q^{\prime}=\frac{1}{2}(q-1)$

Theorem 99
若 $p,q$ 中有一个是 $4n+1$ 型素数，那么
$\left(\frac{p}{q}\right)=\left(\frac{q}{p}\right)$
若 $p,q$ 都是 $4n+3$ 型素数，那么
$\left(\frac{p}{q}\right)=-\left(\frac{q}{p}\right)$

在证明二次互反律之前，我们需要一个引理

Theorem 100
设和式
$S(q, p)=\sum_{s=1}^{p^{\prime}}\left[\frac{s q}{p}\right]$
那么
$S(q, p)+S(p, q)=p^{\prime} q^{\prime}$

我们考虑几何意义，不妨设 $p>q$，如下图所示

点 $A(p,0),B(0,q),K(p',0),L(0,q')$

直线 $OC$ 方程为 $y=\frac{q}{p}x$，因此 $N(p',\frac{p'q}{p})$ 在 $OC$ 上

由于

$k_{OM}=\frac{q'}{p'}=\frac{q-1}{p-1}<\frac{q}{p}=k_{OC}$

因此 $M$ 在 $N$ 点下方

而

$q'<\frac{p'q}{p}<q'+1$

因此 $KM,KN$ 之间没有格点（上面的式子自行推导）

接下来我们用两种方式统计长方形 $OKML$ 内部格点数量，注意，我们统计 $KM,LM$ 边界上的格点，但不统计坐标轴 $OK,OL$ 上的格点

第一种方式就是一个简单的乘法，$Ans=p'q'$

第二种方式是统计由直线 $OC$ 分割而成的两部分的答案然后相加

由于 $(p,q)=1$，因此直线 $OC$ 上没有格点，而三角形 $PMN$ 内部也没有格点（除了 $PM$ 上可能有）

因此，三角形 $ONK,OLP$ 的答案相加就是最终答案

显然，三角形 $ONK$ 的贡献为 $S(q,p)$，$OLP$ 的贡献为 $S(p,q)$，因此

$Ans=S(q,p)+S(p,q)=p'q'$

---

13、Proof of the law of reciprocity

我们使用高斯引理来证明二次互反律，先来考虑 $\left(\frac{q}{p}\right)$，设

$kq=p\left[\frac{kq}{p}\right]+u_k$

其中

$1 \leqslant k \leqslant p^{\prime}, \quad 1 \leqslant u_{k} \leqslant p-1$

若 $u_k=v_k \leq p'$，则 $u_k$ 是极小剩余 $r_i$ 中的一个

若 $u_k=w_k > p'$，则 $u_k-p$ 是极小剩余 $-r_j'$ 中的一个

我们知道 $r_i,r_j'$ 合起来是一个 $1,2,\cdots,p'$ 的排列，设

$R=\sum r_{i}=\sum v_{k}$

$R^{\prime}=\sum r_{j}^{\prime}=\sum\left(p-w_{k}\right)=\mu p-\sum w_{k}$

这样的话，可以得到

$\mu p+\sum v_{k}-\sum w_{k}=R+R^{\prime}=\sum_{v=1}^{p^{\prime}} v=\frac{1}{2}\cdot \frac{p-1}{2}\cdot \frac{p+1}{2}=\frac{p^{2}-1}{8}$

另一方面，把 $kq=p\left[\frac{kq}{p}\right]+u_k$ 对 $k=1\sim p'$ 求和得到

$\frac{1}{8} q\left(p^{2}-1\right)=p S(q, p)+\sum u_{k}=p S(q, p)+\sum v_{k}+\sum w_{k}$

结合这两个式子可以推导出

$\frac{1}{8}\left(p^{2}-1\right)(q-1)=p S(q, p)+2 \sum w_{k}-\mu p$

由于 $q-1$ 是偶数且 $p^2-1\equiv 0(\bmod 8)$，因此左式是偶数，右式也要是偶数，即

$p\left[S(q,p)-\mu\right]\equiv 0 (\bmod 2)$

而 $p$ 是奇数，因此

$S(q,p)\equiv \mu (\bmod 2)$

因此，根据高斯引理

$\left(\frac{q}{p}\right)=(-1)^{\mu}=(-1)^{S(q, p)}$

最后，根据 Theorem 100，

$\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^{S(q, p)+S(p, q)}=(-1)^{p^{\prime} q^{\prime}}$

我们现在用二次互反律证明 Theorem 97，若

$p=10n+k$

其中 $k=1,3,7,9$，那么

$\left(\frac{5}{p}\right)=\left(\frac{p}{5}\right)=\left(\frac{10 n+k}{5}\right)=\left(\frac{k}{5}\right)$

模 $5$ 的二次剩余是 $1,4$，得证

---

14、Test for primality(素数测试)

接下来我们将介绍两个有关素数测试的定理，它们能测出特定形式的数的素性

Theorem 101
若 $p>2$ 且 $h<p$，对于 $n=hp+1$ 或 $n=hp^{2}+1$ 形式的数，若满足
$2^{h} \not \equiv 1, \quad 2^{n-1} \equiv 1(\bmod n)$
则 $n$ 是素数

记 $n=h p^{b}+1$，其中 $b=1,2$，设 $d$ 是 $2$ 的阶 $(\bmod n)$，根据 Theorem 88

$d\nmid h,\quad d|(n-1)\Rightarrow d|hp^b\Rightarrow p|d$

由于 $d|\phi(n)$，因此 $p|\phi(n)$，设 $n=p_{1}^{a_{1}}\cdots p_{k}^{a_{k}}$，则

$\phi(n)=p_{1}^{a_{1}-1} \ldots p_{k}^{a_{k}-1}\left(p_{1}-1\right) \ldots\left(p_{k}-1\right)$

由于 $p\nmid n$，故

$p|\left(p_{1}-1\right) \ldots\left(p_{k}-1\right)$

因此 $n$ 存在一个素因子 $P$ 满足 $P\equiv 1(\bmod p)$

不妨设 $n=Pm$，由于 $n \equiv 1\equiv P(\bmod p)$，有 $m\equiv 1(\bmod p)$

假设 $m>1$，则设

$n=(u p+1)(v p+1), \quad 1 \leqslant u \leqslant v$

$h p^{b-1}=u v p+u+v$

若 $b=1$，则 $h=uvp+u+v$，导出矛盾式：

$p \leqslant u v p<h<p$

若 $b=2$，则 $h p=u v p+u+v, \quad p |(u+v), \quad u+v \geqslant p$，得到

$2 v \geqslant u+v \geqslant p, \quad v>\frac{1}{2} p$

这样的话，

$u v<h<p, \quad u v \leqslant p-2, \quad u \leqslant \frac{p-2}{v}<\frac{2(p-2)}{p}<2$

因此 $u=1$，同样导出矛盾式

$p-1\leq v\leq p-2$

因此 $m=1,n=P$，证毕

Theorem 102
设 $m\geq 2,h<2^m$，且存在奇素数 $p$ 使得 $n=h2^m+1$ 是模 $p$ 的二次非剩余，那么 $n$ 是素数的充要条件为
$p^{\frac{1}{2}(n-1)} \equiv-1(\bmod n)$

首先，若 $n$ 是素数，由于 $n\equiv 1(\bmod 4)$，根据 Theorem 99，

$\left(\frac{p}{n}\right)=\left(\frac{n}{p}\right)=-1$

再结合 Theorem 83，必要性得证

下面证明充分性，设 $P$ 是 $n$ 的素因子，且 $d$ 是 $p$ 的阶 $(\bmod P)$，则

$p^{\frac{1}{2}(n-1)} \equiv-1, \quad p^{n-1} \equiv 1, \quad p^{P-1} \equiv 1 \quad(\bmod P)$

根据 Theorem 88，

$d\nmid \frac{1}{2}(n-1),\quad d|(n-1),\quad d|(P-1)$

$\Rightarrow d \nmid 2^{m-1} h, \quad d\left|2^{m} h, \quad d\right|(P-1)$

因此

$2^{m}|d,\quad 2^{m}|(P-1)$

设 $P=2^{m}x+1$，由于 $n\equiv1\equiv P(\bmod 2^{m})$，得到 $\frac{n}{P}\equiv 1(\bmod 2^{m})$

$n=\left(2^{m} x+1\right)\left(2^{m} y+1\right), \quad x \geqslant 1, y \geqslant 0$

故

$h=\frac{n-1}{2^{m}}=2^{m}xy+x+y$

因此

$2^{m} x y<2^{m} x y+x+y=h<2^{m}$

得到 $y=0,n=P$，证毕

如果我们令 $h=1,m=2^{k}$，那么 $n=F_k$ 是一个费马数

由于

$1^{2} \equiv 2^{2} \equiv 1,\quad F_k\equiv 2(\bmod 3)$

因此 $F_k$ 是二次非剩余 $(\bmod 3)$

因此 $F_k$ 是素数的充要条件是

$F_{k} |\left(3^{\frac{1}{2}\left(F_{k}-1\right)}+1\right)$

---

15、Factors of Mersenne numbers(梅森数的因子)

现在我们回到第二章中梅森数的问题，关于梅森数 $M_{p}=2^{p}-1$ 的可分解性，欧拉提出过一个简单的定理

Theorem 103
若 $k>1$ 且 $p=4k+3$ 是素数，那么 $2p+1$ 是素数的充要条件是
$2^{p} \equiv 1(\bmod 2 p+1)$
也就是说，若 $2p+1$ 是素数，则 $(2p+1)|M_{p}$

首先证明必要性，设 $2p+1=P$ 是素数，由于 $P\equiv 7(\bmod 8)$，根据 Theorem 95，

$\left(\frac{2}{P}\right)=1$

因此

$2^{p}=2^{\frac{1}{2}(P-1)} \equiv 1(\bmod P)$

接下来证明充分性，在 Theorem 101 中，令 $h=2,n=2p+1$，显然 $h<p$，且

$2^h=4\not\equiv 1,\quad 2^{n-1}=2^{2p}\equiv 1(\bmod n)$

因此 $n=2p+1$ 是素数，证毕

---

Notes

设 $q$ 是模 $p$ 的最小正二次非剩余，我们可以用 Theorem 85 找一个 $q$ 的上界

设 $m=\left[\frac{p}{q}\right]+1$，则

$p<mq<p+q,\quad 0<mq-p<q$

因此 $mq-p$ 是模 $p$ 的二次剩余，即

$\left(\frac{mq}{p}\right)=\left(\frac{mq-p}{p}\right)=1$

根据 Theorem 85，

$\left(\frac{q}{p}\right)=-1\Rightarrow \left(\frac{m}{p}\right)=-1$

因此 $q<m$，进而得到上界

$q^2<p+q\Rightarrow q<\sqrt{p+\frac{1}{4}}+\frac{1}{2}$

Burgess(伯吉斯) 证明了当 $p\rightarrow \infty$ 时 $q=O\left(p^{a}\right)$，其中常数 $a>\frac{1}{4}e^{-\frac{1}{2}}$