第五章 同余与剩余

1、Highest common divisor and least common multiple(最大公约数与最小公倍数)

我们已经定义了两个数 a,ba,b 的最大公约数为 (a,b)(a,b)，它有一个计算公式

Theorem 50
若
a=∏ppα(α⩾0),b=∏ppβ(β⩾0)a=\prod_{p} p^{\alpha}(\alpha \geqslant 0),\quad b=\prod_{p} p^{\beta}(\beta \geqslant 0)
那么
(a,b)=∏ppmin⁡(α,β)(a, b)=\prod_{p} p^{\min (\alpha, \beta)}

其中 min⁡(a,b)\min(a,b) 表示 a,ba,b 中较小的数，该定理通过算术基本定理很容易证明

a,ba,b 的最小公倍数 {a,b}\{a, b\} 定义为能整除这两个数的最小整数

Theorem 51
沿用 Theorem 50 的定义，则有
{a,b}=∏ppmax⁡(α,β)\{a, b\}=\prod_{p} p^{\max (\alpha, \beta)}

由上述两个定理，我们可以导出

Theorem 52
{a,b}=ab(a,b)\{a, b\}=\frac{a b}{(a, b)}

如果 (a,b)=1(a,b)=1，那么我们称 a,ba,b 是 coprime(互质的)

我们称 a,b,c,⋯ ,ka,b,c,\cdots,k 是互质的，意思是它们中的任意两个数互质，这个条件比

(a,b,c,…,k)=1(a, b, c, \ldots, k)=1

要强，因为后者只需要这些数中没有大于 11 的公因子即可

2、Congruences and classes of residus(同余与剩余系)

如果 mm 是 (x−a)(x-a) 的因子，那么我们称 xx 与 aa 模 mm 同余，记为

x≡a( mod m)x \equiv a(\bmod m)

根据定义我们知道

x≡a( mod m)⇔m∣(x−a)x \equiv a(\bmod m) \Leftrightarrow m|(x-a)

如果 x≡a( mod m)x \equiv a(\bmod m)，那么 aa 称为 xx 模 mm 的 residus(剩余)

特别地，如果 0≤a<m0\leq a<m，那么 aa 称为 xx 模 mm 的最小非负剩余

因此，若 a≡b( mod m)a\equiv b(\bmod m)，那么 a,ba,b 对于模 mm 有相同的剩余

我们用剩余系刻画与模 mm 下的一个剩余同余的所有数，每一个剩余系中的数都可以用来表示这个剩余系，因此共有 mm 个剩余类

0,1,2,⋯ ,m−10,1,2,\cdots,m-1

他们共同组成了模 mm 下的 complete system(完全剩余系)

同余符号也可以用于非整数的情况，我们用

x≡y( mod z)x\equiv y(\bmod z)

表示 (x−y)(x-y) 是 zz 的整数倍，比如

32≡12( mod 1),−π≡π( mod 2π)\frac{3}{2} \equiv \frac{1}{2}(\bmod 1), \quad-\pi \equiv \pi(\bmod 2 \pi)

3、Elementary properties of congruences(同余的性质)

对于模数 mm，同余显然满足如下性质：

（1）a≡b→b≡aa \equiv b \rightarrow b \equiv a

（2）a≡b,b≡c→a≡ca \equiv b,b \equiv c \rightarrow a \equiv c

（3）a≡a′,b≡b′→a+b≡a′+b′a \equiv a^{\prime},b \equiv b^{\prime} \rightarrow a+b \equiv a^{\prime}+b^{\prime}

如果 a≡a′,b≡b′,…a \equiv a^{\prime}, b \equiv b^{\prime}, \ldots 我们有

（4）ka+lb+…≡ka′+lb′+…k a+l b+\ldots \equiv k a^{\prime}+l b^{\prime}+\ldots

（5）a2≡a′2,a3≡a′3,…a^{2} \equiv a^{\prime 2}, a^{3} \equiv a^{\prime 3},\ldots

因此，我们导出最终版的结论，如果 ϕ(a,b,…)\phi(a, b, \ldots) 是整系数多项式

（6）ϕ(a,b,…)≡ϕ(a′,b′,…)\phi(a, b, \ldots) \equiv \phi\left(a^{\prime}, b^{\prime}, \ldots\right)

Theorem 53
如果 a≡b( mod m),a≡b( mod n)a\equiv b(\bmod m),a\equiv b(\bmod n)，那么
a≡b( mod {m,n})a \equiv b(\bmod \{m, n\})

设 {m,n}=∏ppc\{m,n\}=\prod_{p} p^{c}，那么对于每一个 pcp^c，有 pc∣mp^c|m 或 pc∣np^c|n，因此 pc∣(a−b)p^c|(a-b)

由于所有的 pp 都是互质的，所以 {m,n}∣(a−b)\{m,n\}|(a-b)，即

a≡b( mod {m,n})a \equiv b(\bmod \{m, n\})

该定理可以推广到非整数同余的情况

4、Linear congruences(线性同余)

刚才我们列出的 66 个性质有点类似于线性代数中的式子，但是随后我们发现把它反过来

ka≡ka′→a≡a′k a \equiv k a^{\prime} \rightarrow a \equiv a^{\prime}

不一定成立，比如

2⋅2≡2⋅4( mod 4)2\cdot 2\equiv 2\cdot 4(\bmod 4)

但是

2≢4( mod 4)2\not\equiv 4(\bmod 4)

接下来，我们考虑这个反过来的式子在什么情况下是成立的

Theorem 54
如果 (k,m)=d(k,m)=d，那么
ka≡ka′( mod m)→a≡a′( mod md)k a \equiv k a^{\prime}(\bmod m) \rightarrow a \equiv a^{\prime}\left(\bmod \frac{m}{d}\right)
逆命题同样成立

我们设

k=k1d,m=m1d,(k1,m1)=1k=k_{1} d, \quad m=m_{1} d, \quad\left(k_{1}, m_{1}\right)=1

那么

k(a−a′)m=k1(a−a′)m1\frac{k (a-a^{\prime})}{m}=\frac{k_{1}\left(a-a^{\prime}\right)}{m_{1}}

由于 (k1,m1)=1(k_{1},m_{1})=1，因此 m1∣(a−a′)m_{1}|(a-a^{\prime})，即

a≡a′( mod md)a\equiv a^{\prime}(\bmod \frac{m}{d})

证明了这个定理，我们的问题也就随之解决了

Theorem 55
如果 (k,m)=1(k,m)=1，那么
ka≡ka′→a≡a′( mod m)k a \equiv k a^{\prime} \rightarrow a \equiv a^{\prime}(\bmod m)

Theorem 56
如果 a1,a2,⋯ ,ama_1,a_2,\cdots,a_m 是模 mm 下的完全剩余系，且 (k,m)=1(k,m)=1，那么 ka1,ka2,⋯ ,kamka_1,ka_2,\cdots,ka_m 也是模 mm 下的完全剩余系

根据 Theorem 55

kai≡kaj( mod m)→ai≡aj( mod m)ka_i\equiv ka_j(\bmod m)\rightarrow a_i\equiv a_j(\bmod m)

这个式子成立当且仅当 i=ji=j，证毕

更一般地，如果 (k,m)=1(k,m)=1，那么

kar+l(r=1,2,3,…,m)k a_{r}+l(r=1,2,3, \ldots, m)

也是模 mm 下的完全剩余系

Theorem 57
如果 (k,m)=d(k,m)=d，那么同余方程
kx≡l( mod m)kx\equiv l(\bmod m)
有解当且仅当 d∣ld|l，且方程解数为 dd

这个同余方程等价于

kx−my=lkx-my=l

由 Theorem 25，方程有解条件为 d∣ld|l

很多初学者可能无法理解，定理中描述解数为 dd 是什么意思，明明方程有无穷多的解啊

这里，我们把属于同一剩余系的解看作是相同的

当 d=1d=1 时，很显然这是 Theroem 56 的推论，方程左边的 kxkx 构成了模 mm 下的完全剩余系，方程自然仅有 11 个解

当 d>1d>1 时，设

m=dm′,k=dk′,l=dl′m=d m^{\prime}, \quad k=d k^{\prime}, \quad l=d l^{\prime}

那么原同余方程等价于

k′x≡l′( mod m′)k^{\prime} x \equiv l^{\prime}\left(\bmod m^{\prime}\right)

由于 (k′,m′)=1\left(k^{\prime}, m^{\prime}\right)=1，方程仅有 11 解，设

x≡t( mod m′)x \equiv t\left(\bmod m^{\prime}\right)

是方程的解，那么

x=t+m′yx=t+m^{\prime}y

接下来回到模 mm 下，考察 t+m′yt+m^{\prime}y 的取值个数，由于

t+ym′≡t+zm′( mod m)⇔m∣m′(y−z)⇔d∣(y−z)t+y m^{\prime} \equiv t+z m^{\prime}(\bmod m) \Leftrightarrow m\left|m^{\prime}(y-z) \Leftrightarrow d\right|(y-z)

因此方程有 dd 个解，分别为

t,t+m′,t+2m′,…,t+(d−1)m′t, \quad t+m^{\prime}, \quad t+2 m^{\prime}, \ldots, \quad t+(d-1) m^{\prime}

这里博主惊奇的发现我这近 600600 大洋的书竟然出现了印刷错误（口吐芬芳中），有图为证：

5、Euler's function ϕ(m)\phi(m)(欧拉函数)

我们定义 ϕ(m)\phi(m) 表示区间 [1,m][1,m] 中与 mm 互质的数的个数

如果 (a,m)=1(a,m)=1，那么剩余类 x≡a( mod m)x\equiv a(\bmod m) 中的所有数都与 mm 互质，这 ϕ(m)\phi(m) 个剩余类组成了 complete set of residues prime to m(简化剩余系)

Theorem 58
如果 a1,a2,…,aϕ(m)a_1,a_2,\ldots,a_{\phi(m)} 是简化剩余系且 (k,m)=1(k,m)=1，那么
ka1,ka2,…,kaϕ(m)ka_1,ka_2,\ldots,ka_{\phi(m)}
也是简化剩余系

由于 (kai,m)=1(ka_i,m)=1，那么沿用之前的方法，很容易证明该定理

Theorem 59
设 (m,m′)=1(m,m^{\prime})=1，aa 取遍模 mm 的完全剩余系中的值，a′a'取遍模 m′m' 的完全剩余系中的值，那么 a′m+am′a'm+am' 取遍了模 mm′mm' 的完全剩余系中的值

a′m+am′a'm+am' 共有 mm′mm' 个取值，假设

a1′m+a1m′≡a2′m+a2m′( mod mm′)a_{1}^{\prime} m+a_{1} m^{\prime} \equiv a_{2}^{\prime} m+a_{2} m^{\prime}\left(\bmod m m^{\prime}\right)

a1m′≡a2m′( mod m)a_{1} m^{\prime} \equiv a_{2} m^{\prime}(\bmod m)

由于 (m,m′)=1(m,m')=1

a1≡a2,a1′≡a2′a_1\equiv a_2,\quad a_1'\equiv a_2'

因此这 mm′mm' 个取值两两不同余，它们构成了完全剩余系 ( mod mm′)(\bmod mm')

如果函数 f(x)f(x) 满足对于 (m,m′)=1(m,m')=1，都有

f(mm′)=f(m)f(m′)f(mm')=f(m)f(m')

那么我们称 f(x)f(x) 是 multiplicative function(积性函数)

Theorem 60
ϕ(n)是积性函数\phi(n) 是积性函数

设 (m,m′)=1(m,m')=1，根据 Theorem 59，当 aa 取遍模 mm 的完全剩余系中的值，a′a'取遍模 m′m' 的完全剩余系中的值，那么 a′m+am′a'm+am' 取遍了模 mm′mm' 的完全剩余系中的值，且

(a′m+am′,mm′)=1⇔(a′m+am′,m)=1且(a′m+am′,m′)=1⇔(am′,m)=1且(a′m,m′)=1⇔(a,m)=1且(a′,m′)=1\begin{aligned}\left(a^{\prime} m+a m^{\prime}, m m^{\prime}\right)=1 & \Leftrightarrow\left(a^{\prime} m+a m^{\prime}, m\right)=1 且\left(a^{\prime} m+a m^{\prime}, m^{\prime}\right)=1 \\ & \Leftrightarrow\left(a m^{\prime}, m\right)=1 且\left(a^{\prime} m, m^{\prime}\right)=1 \\ & \Leftrightarrow(a, m)=1 且\left(a^{\prime}, m^{\prime}\right)=1 \end{aligned}

满足 (a,m)=1且(a′,m′)=1(a,m)=1且(a',m')=1 的数对 (a,a′)(a,a') 共有 ϕ(m)ϕ(m′)\phi(m)\phi(m') 个

满足 (a′m+am′,mm′)=1\left(a^{\prime} m+a m^{\prime}, m m^{\prime}\right)=1 的数对 (a,a′)(a,a') 共有 ϕ(mm′)\phi(mm') 个，因此

ϕ(mm′)=ϕ(m)ϕ(m′)\phi(mm')=\phi(m)\phi(m')

事实上，在刚才的证明过程中，我们本质上证明了下面的定理

Theorem 61
设 (m,m′)=1(m,m^{\prime})=1，aa 取遍模 mm 的简化剩余系中的值，a′a'取遍模 m′m' 的简化剩余系中的值，那么 a′m+am′a'm+am' 取遍了模 mm′mm' 的简化剩余系中的值

根据 Theorem 60，如果我们求出了素数的幂的欧拉函数值，那么我们就能求出任意整数的欧拉函数值

对于素数 pp，小于 pcp^c 的整数有 pc−1p^c-1 个，与 pcp^c 不互质的数必须含有因子 pp，因此与 pcp^c 不互质的数共有 pc−1−1p^{c-1}-1 个，故

ϕ(pc)=pc−1−(pc−1−1)=pc(1−1p)\phi\left(p^{c}\right)=p^{c}-1-\left(p^{c-1}-1\right)=p^{c}\left(1-\frac{1}{p}\right)

更一般地，有如下定理

Theorem 62
若 m=Πppcm=\Pi_p p^{c}，那么
ϕ(m)=m∏p(1−1p)\phi(m)=m \prod_{p}\left(1-\frac{1}{p}\right)

除此之外，我们还能得到一个非常重要的定理

Theorem 63
∑d∣mϕ(d)=m\sum_{d | m} \phi(d)=m

设 m=Πppcm=\Pi_p p^{c}，那么

Φ(m)=∑d∣mϕ(d)=∑c′=0c∏pϕ(pc′)=∏p{1+ϕ(p)+ϕ(p2)+⋯+ϕ(pc)}\begin{aligned} \Phi(m) &=\sum_{d | m} \phi(d)=\sum_{c^{\prime}=0}^{c} \prod_{p} \phi\left(p^{c^{\prime}}\right) \\ &=\prod_{p}\left\{1+\phi(p)+\phi\left(p^{2}\right)+\cdots+\phi\left(p^{c}\right)\right\} \end{aligned}

由于

1+ϕ(p)+⋯+ϕ(pc)=1+(p−1)+p(p−1)+⋯+pc−1(p−1)=pc1+\phi(p)+\cdots+\phi\left(p^{c}\right)=1+(p-1)+p(p-1)+\cdots +p^{c-1}(p-1)=p^{c}

因此

Φ(m)=∏ppc=m\Phi(m)=\prod_{p} p^{c}=m

6、Trigonometrical sum(三角和)

在数论中，有三类非常重要的三角和，它们有着类似于积性函数的优美的性质，其证明中用到了 Theorem 59 和 Theorem 61

我们记

e(τ)=e2πiτ,(τ∈Q)e(\tau)=e^{2 \pi i \tau},\quad(\tau\in Q)

注：eζ=1+ζ+ζ22!⋯e^{\zeta}=1+\zeta+\frac{\zeta^{2}}{2!}\cdots，ζ\zeta 是复数

显然，如果 m≡m′( mod n)m \equiv m^{\prime}(\bmod n)，那么有

e(mn)=e(m′n)e\left(\frac{m}{n}\right)=e\left(\frac{m^{\prime}}{n}\right)

这个性质使得三角和在数论中有着重要的地位

（1）Gauss's sum(高斯和)

高斯和在二次剩余领域有非常重要的用处

S(m,n)=∑h=0n−1e2πih2m/n=∑h=0n−1e(h2mn)S(m, n)=\sum_{h=0}^{n-1} e^{2 \pi i h^{2} m / n}=\sum_{h=0}^{n-1} e\left(\frac{h^{2} m}{n}\right)

根据刚才介绍的同余性质，我们可以写为

S(m,n)=∑h(n)e(h2mn)S(m, n)=\sum_{h(n)} e\left(\frac{h^{2} m}{n}\right)

其中，h(n)h(n) 表示 hh 属于模 nn 的完全剩余系

Theorem 64
如果 (n,n′)=1(n,n')=1，那么
S(m,nn′)=S(mn′,n)S(mn,n′)S\left(m, n n^{\prime}\right)=S\left(m n^{\prime}, n\right) S\left(m n, n^{\prime}\right)

设 h,h′h,h' 分别取遍模 n,n′n,n' 完全剩余系中的值，那么根据 Theorem 59，

H=hn′+h′nH=h n^{\prime}+h^{\prime} n

取遍模 nn′nn' 完全剩余系中的值，另外有

mH2=m(hn′+h′n)2≡mh2n2+mh2n2( mod nn′)m H^{2}=m\left(h n^{\prime}+h^{\prime} n\right)^{2} \equiv m h^{2} n^{2}+m h^{2} n^{2}\left(\bmod n n^{\prime}\right)

因此

S(mn′,n)S(mn,n′)={∑h(n)e(h2mn′n)}{∑h′(n)e(h′2mnn′)}=∑h(n),h′(n)e(h2mn′n+h′2mnn′)=∑h(n),h′(n)e(m(h2n′2+h′2n2)nn′)=∑H(nn′)e(mH2nn′)=S(m,nn′)\begin{aligned} S\left(m n^{\prime}, n\right) S\left(m n, n^{\prime}\right) &=\left\{\sum_{h(n)} e\left(\frac{h^{2} m n^{\prime}}{n}\right)\right\}\left\{\sum_{h^{\prime}(n)} e\left(\frac{h^{\prime 2} m n}{n^{\prime}}\right)\right\} \\ &=\sum_{h(n), h^{\prime}(n)} e\left(\frac{h^{2} m n^{\prime}}{n}+\frac{h^{\prime 2} m n}{n^{\prime}}\right) \\ &=\sum_{h(n), h^{\prime}(n)} e\left(\frac{m\left(h^{2} n^{\prime 2}+h^{\prime 2} n^{2}\right)}{n n^{\prime}}\right) \\ &=\sum_{H(nn')} e\left(\frac{m H^{2}}{n n^{\prime}}\right)=S\left(m, n n^{\prime}\right) \end{aligned}

（2）Ramanujan's sum(拉马努金和)

定义拉马努金和为

cq(m)=∑h∗(q)e(hmq)c_{q}(m)=\sum_{h^{*}(q)} e\left(\frac{h m}{q}\right)

其中 h∗(q)h^{*}(q) 表示模 qq 的简化剩余系，拉马努金和还有另外一种形式，我们需要先了解一点其它的东西

我们称 ρ\rho 为 primitive q-th root of unity(q次单位原根) 如果 ρq=1\rho^{q}=1 且不存在比 qq 小的整数 rr 满足 ρr=1\rho^{r}=1

假设 ρq=1\rho^{q}=1，rr 是最小的满足 ρr=1\rho^{r}=1 的正整数，我们设 q=kr+sq=kr+s，其中 0≤s<r0\leq s<r，那么

ρs=ρq−kr=1\rho^{s}=\rho^{q-k r}=1

因此 s=0→r∣qs=0\rightarrow r|q，所有有下述定理

Theorem 65
如果 qq 次单位根是 rr 次单位原根，那么 rr 必为 qq 的因子

Theorem 66
所有的 qq 次单位根是如下的数：
e(hq)(h=0,1,…,q−1)e\left(\frac{h}{q}\right) \quad(h=0,1, \ldots, q-1)
该单位根是单位原根的充要条件是 (h,q)=1(h,q)=1

现在我们写出拉马努金和的另一种形式：

cq(m)=∑ρ∈{q次单位原根}ρmc_{q}(m)=\sum_{\rho\in\{q次单位原根\} } \rho^{m}

Theorem 67
如果 (q,q′)=1(q,q')=1，那么
cqq′(m)=cq(m)cq′(m)c_{q q^{\prime}}(m)=c_{q}(m) c_{q^{\prime}}(m)

根据 Theorem 61，

cq(m)cq′(m)=∑h∗(q),h′∗(q)e{m(hq+h′q′)}=∑h∗(q),h′∗(q)e{m(hq′+h′q)qq′}=cqq′(m)\begin{aligned} c_{q}(m) c_{q^{\prime}}(m) &=\sum_{h^{*}(q), h^{\prime *}(q)} e\left\{m\left(\frac{h}{q}+\frac{h^{\prime}}{q^{\prime}}\right)\right\} \\ &=\sum_{h^{*}(q), h^{\prime *}(q)} e\left\{\frac{m\left(h q^{\prime}+h^{\prime} q\right)}{q q^{\prime}}\right\}=c_{q q^{\prime}}(m) \end{aligned}

感觉我可以把这个积性函数出成 OIOI 毒瘤题

（3）Kloosterman's sum

Kloosterman's 和更为晦涩难懂，

S(u,v,n)=∑h∗(n)e(uh+vh‾n)S(u, v, n)=\sum_{h^{*}(n)} e\left(\frac{u h+v \overline{h}}{n}\right)

其中 h‾\overline{h} 定义为模 nn 下的乘法逆元：

hh‾≡1( mod n)h\overline{h}\equiv 1(\bmod n)

Theorem 57 保证了这样的乘法逆元 h‾\overline{h} 存在且唯一

Theorem 68
如果 (n,n′)=1(n,n')=1，那么
S(u,v,n)S(u,v′,n′)=S(u,V,nn′)S(u, v, n) S\left(u, v^{\prime}, n^{\prime}\right)=S\left(u, V, n n^{\prime}\right)
其中，
V=vn′2+v′n2V=v n^{\prime 2}+v^{\prime} n^{2}

S(u,v,n)S(u,v′,n′)=∑h∗(q),h′∗(q)e(uh+vh‾n+uh′+v′h‾′n′)=∑h∗(q),h′∗(q)e{u(hn+h′nnn′)+vh‾n′+v′h‾′nnn′}=∑h∗(q),h′∗(q)e(uH+Knn′)\begin{aligned} S(u, v, n) S\left(u, v^{\prime}, n^{\prime}\right) &=\sum_{h^{*}(q), h^{\prime *}(q)} e\left(\frac{u h+v \overline{h}}{n}+\frac{u h^{\prime}+v^{\prime} \overline{h}^{\prime}}{n^{\prime}}\right) \\ &=\sum_{h^{*}(q), h^{\prime *}(q)} e\left\{u\left(\frac{h n+h^{\prime} n}{n n^{\prime}}\right)+\frac{v \overline{h} n^{\prime}+v^{\prime} \overline{h}^{\prime} n}{n n^{\prime}}\right\} \\ &=\sum_{h^{*}(q), h^{\prime *}(q)} e\left(\frac{u H+K}{n n^{\prime}}\right) \end{aligned}

这里

H=hn′+h′n,K=vh‾n′+v′h′nH=h n^{\prime}+h^{\prime} n, \quad K=v \overline{h} n^{\prime}+v^{\prime} h^{\prime} n

根据 Theorem 61，HH 取遍模 nn′nn' 简化剩余系中的所有值，那么现在我们只需要证明

K≡VH‾( mod nn′)K \equiv V \overline{H}\left(\bmod n n^{\prime}\right)

即可完成

S(u,v,n)S(u,v′,n′)=∑He(uH+VH‾nn′)=S(u,V,nn′)S(u, v, n) S\left(u, v^{\prime}, n^{\prime}\right)=\sum_{H} e\left(\frac{u H+V \overline{H}}{n n^{\prime}}\right)=S\left(u, V, n n^{\prime}\right)

现在，我们知道

(hn′+h′n)H‾=HH‾≡1( mod nn′)\left(h n^{\prime}+h^{\prime} n\right) \overline{H}=H \overline{H} \equiv 1\left(\bmod n n^{\prime}\right)

因此

hn′H‾≡1( mod n),n′H‾≡h‾hn′H‾≡h‾( mod n)h n^{\prime} \overline{H} \equiv 1(\bmod n), \quad n^{\prime} \overline{H} \equiv \overline{h} h n^{\prime} \overline{H} \equiv \overline{h}(\bmod n)

所以

n′2H‾≡n′h‾( mod nn′)n^{\prime 2} \overline{H} \equiv n^{\prime} \overline{h}\left(\bmod n n^{\prime}\right)

类似的，取另一部分可以得到

n2H‾≡n′h‾′( mod nn′)n^{2} \overline{H} \equiv n^{\prime} \overline{h}^{\prime}\left(\bmod n n^{\prime}\right)

这样我们就推导出了

VH‾=(vn′2+v′n2)H‾≡vn′h‾′+v′nh‾′≡K( mod nn′)V \overline{H}=\left(v n^{\prime 2}+v^{\prime} n^{2}\right) \overline{H} \equiv v n^{\prime} \overline{h}^{\prime}+v^{\prime} n \overline{h}^{\prime} \equiv K\left(\bmod n n^{\prime}\right)

定理随之证毕

7、General principle(定理的推广)

我们回到 Theorem 65，如果我们用另一种方式描述定理，可能会省去大量的重复工作

我们用 P(a)P(a) 表示关于非负整数 aa 的一条性质

Theorem 69
如果 P(a),P(b)P(a),P(b) 能推导出 P(a+b),P(a−b)(a≥b)P(a+b),P(a-b)(a\geq b)，且 rr 是满足 P(r)P(r) 为真的最小正整数，那么
（1）P(kr)P(kr) 为真，其中 kk 是任意非负整数
（2）任何满足 P(q)P(q) 为真的 qq 都是 rr 的倍数

（1）是非常显然的

（2）注意到 0<r≤q0<r\leq q，设

q=kr+s,s=q−krq=k r+s, \quad s=q-k r

其中 k≥1,0≤s<rk\geq 1,0\leq s<r，由于 P(r)→P(kr)P(r)\rightarrow P(kr)

P(q),P(kr)→P(s)P(q),P(k r) \rightarrow P(s)

根据 rr 的定义，ss 只能等于 00，证毕

取 P(a)：ρa=1P(a)：\rho^{a}=1 就得到了 Theorem 65 的情况