哈代数论读书笔记(六)——费马定理与二次剩余

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(Gauss’s Lemma)
$$\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}}$

此条目发表在数学, 数论分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注