第七章 同余方程

---

1、Roots of congruences(同余方程的根)

满足同余方程

$f(x)=c_{0} x^{n}+c_{1} x^{n-1}+\ldots+c_{n} \equiv 0(\bmod m)$

的 $x$ 称为同余方程的 root(根)，如果 $a$ 是同余方程的根，那么与 $a$ 同余的数都是方程的根，同余的根我们视为等价的，因此，当我们说一个同余方程有 $l$ 个根时，指的是方程有 $l$ 个不同余的根

根据分析学的成果，我们知道 $n$ 次代数方程在复数范围内有且仅有 $n$ 个根，且 $n$ 次多项式可以分解为 $n$ 个线性因子的乘积，我们自然而然的想到去探究同余方程有没有类似的性质，然而下面的几个例子告诉我们同余方程的性质并非这么简单

我们知道根据欧拉定理，方程

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

有 $p-1$ 个根，分别为 $1,2, \ldots, p-1$

而方程

$x^{4}-1 \equiv 0(\bmod 16)$

有 $8$ 个根，分别为 $1,3,5,7,9,11,13,15$

下面的方程方程则没有根

$x^{4}-2 \equiv 0(\bmod 16)$

由此可见，同余方程的性质比代数方程要复杂得多

---

2、Integral polynomials and identical congruences(整多项式及其同余)

若 $c_{0}, c_{1}, \ldots, c_{n}$ 是整数，那么

$c_{0} x^{n}+c_{1} x^{n-1}+\cdots+c_{n}$

称为 integral polynomial(整多项式)，若

$f(x)=\sum_{r=0}^{n} c_{r} x^{n-r}, \quad g(x)=\sum_{r=0}^{n} c_{r}^{\prime} x^{n-r}$

满足 $c_{r} \equiv c_{r}^{\prime}(\bmod m)$，那么我们称 $f(x),g(x)$ 同余 $(\bmod m)$，记作

$f(x) \equiv g(x)(\bmod m)$

若另有一个整多项式 $h(x)$，那么

$f(x) \equiv g(x) \rightarrow f(x) h(x) \equiv g(x) h(x)$

Theorem 104
（1）若 $p$ 是素数，且
$f(x) g(x) \equiv 0(\bmod p)$
那么 $f(x) \equiv 0$ 或 $g(x) \equiv 0(\bmod p)$
（2）更一般的，若
$f(x) g(x) \equiv 0\left(\bmod p^{a}\right),\quad f(x) \not\equiv 0(\bmod p)$
那么 $g(x) \equiv 0(\bmod p^{a})$

（1）我们设 $f_{1}(x),g_{1}(x)$ 分别是 $f(x),g(x)$ 删掉被 $p$ 整除的项之后的结果

假设 $f(x) \not\equiv 0,g(x) \not\equiv 0$，那么 $f_{1}(x),g_{1}(x)$ 中的第一项系数不能被 $p$ 整除，因此 $f_{1}(x)g_{1}(x)$ 的第一项系数也不能被 $p$ 整除

$f(x) g(x) \equiv f_{1}(x) g_{1}(x) \not\equiv 0(\bmod p)$

（2）我们把 $f(x)$ 中系数是 $p$ 的倍数的项删掉，$g(x)$ 中系数是 $p^{a}$ 的倍数的项删掉，那么用同样的方法就可以证明，定理的这一部分将在第八章用到

值得注意的是，若 $f(x) \equiv g(x)$，那么 $f(a)\equiv g(a)$ 对于所有的 $a$ 成立，但是反过来不一定成立，例如

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

对于所有的 $a$ 成立，但是

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

显然不成立

---

3、Divisibility of polynomials(多项式的整除性)

如果存在一个整多项式 $h(x)$ 使得

$f(x) \equiv g(x) h(x)(\bmod m)$

那么我们称 $f(x)$ 能被 $g(x)$ 整除 $(\bmod m)$，记作

$g(x)|f(x)(\bmod m)$

Theorem 105
使得
$(x-a)|f(x)(\bmod m)$
成立的一个充要条件是
$f(a)\equiv 0(\bmod m)$

若 $(x-a)|f(x)(\bmod m)$，那么存在 $h(x)$ 使得

$f(x) \equiv(x-a) h(x)(\bmod m)$

因此 $f(a)\equiv 0(\bmod m)$，必要性得证

若 $f(a)\equiv 0(\bmod m)$，那么

$f(x) \equiv f(x)-f(a)(\bmod m)$

设 $f(x)=\sum c_{r} x^{n-r}$，那么

$f(x)-f(a)=(x-a) h(x)$

其中

$h(x)=\frac{f(x)-f(a)}{x-a}=\sum c_{r}\left(x^{n-r-1}+x^{n-r-2} a+\cdots+a^{n-r-1}\right)$

也就是说，存在 $h(x)$ 使得

$f(x)\equiv (x-a)h(x)(\bmod m)$

即 $(x-a)|f(x)(\bmod m)$，证毕

---

4、Roots of congruences to a prime modulus(模素数意义下同余方程的根)

Theorem 106
若 $p$ 是素数，且
$f(x) \equiv g(x) h(x)(\bmod p)$
那么 $f(x)$ 的根是 $g(x)$ 或 $h(x)$ 的根 $(\bmod m)$

设 $a$ 是 $f(x)$ 的根，那么

$f(a) \equiv g(a)h(a)\equiv 0(\bmod p)$

因此 $g(a)\equiv 0$ 或 $h(a)\equiv 0$，因此 $a$ 是 $g(x)$ 或 $h(x)$ 的根 $(\bmod m)$

这里，模数 $p$ 是素数的条件是必要的，例如

$x^{2} \equiv x^{2}-4 \equiv(x-2)(x+2)(\bmod 4)$

$4$ 是 $x^2\equiv 0(\bmod 4)$ 的根，但不是 $x-2\equiv 0(\bmod 4)$ 或 $x+2\equiv 0(\bmod 4)$ 的根

Theorem 107
若 $f(x)$ 是 $n$ 次多项式，且有多于 $n$ 个根 $(\bmod p)$，那么
$f(x)\equiv 0(\bmod p)$

这个定理等价于 $n$ 次非零多项式至多有 $n$ 个根，我们用数学归纳法证明

当 $n=1$ 时，根据 Theorem 57 显然成立

假设当 $f(x)$ 次数小于 $n$ 时成立，那么当次数等于 $n$ 时，设 $f(a)\equiv 0$

$f(x)\equiv (x-a)g(x)(\bmod p)$

根据 Theorem 106，$f(x)$ 的根要么是 $a$，要么是 $g(x)$ 的根，若 $f(x)$ 有多于 $n$ 个根，那么 $g(x)$ 有多于 $n-1$ 个根，因此

$g(x)\equiv 0\Rightarrow f(x)\equiv 0(\bmod p)$

这里，模数 $p$ 是素数的条件也是必要的，例如

$x^{4}-1\equiv 0(\bmod 16)$

有 $8$ 个根，事实上刚才的过程已经证明了下面的定理

Theorem 108
若 $f(x)$ 所有的根为 $a_{1}, a_{2}, \ldots, a_{n}(\bmod p)$，那么
$f(x) \equiv c_{0}\left(x-a_{1}\right)\left(x-a_{2}\right) \ldots\left(x-a_{n}\right)(\bmod p)$

---

5、Some applications of the general theorems(扩展理论的应用)

我们知道根据费马定理，当 $d=p-1$ 时，同余方程

$x^{d} \equiv 1(\bmod p)$

有 $p-1$ 个根，我们接下来证明当 $d|(p-1)$ 时，结论也是正确的

Theorem 109
若 $p$ 为素数且 $d|(p-1)$，那么同余方程
$x^{d} \equiv 1(\bmod p)$
有 $d$ 个根

我们有 $x^{p-1}-1=\left(x^{d}-1\right) g(x)$，其中

$g(x)=x^{p-1-d}+x^{p-1-2 d}+\cdots+x^{d}+1$

由于 $x^{p-1}-1\equiv 0$ 有 $p-1$ 个根，根据 Theorem 106，$g(x)\equiv 0$ 最多有 $p-1-d$ 个根，因此 $x^{d}-1\equiv 0$ 至少有 $d$ 个根

结合 $x^{d}-1\equiv 0$ 至多有 $d$ 个根，即可证明有且仅有 $d$ 个根

在这 $d$ 个根中，有些以 $d$ 为阶，另外的一些则是以更小的 $p-1$ 的因子为阶，接下来的定理将给出以 $d$ 为阶的根的个数

Theorem 110
在同余方程
$x^{d}\equiv 1(\bmod p)$
的所有根中，有 $\phi(d)$ 个根以 $d$ 为阶

设 $\psi(d)$ 表示以 $d$ 为阶的根的个数，那么

$\sum_{d | (p-1)} \psi(d)=p-1$

根据 Theorem 63，有

$\sum_{d | (p-1)} \phi(d)=p-1$

那么接下来只需要证明 $\psi(d)\leq \phi(d)$ 即可证明 $\psi(d)=\phi(d)$

若 $\psi(d)>0$，那么至少有一个根 $f$ 以 $d$ 为阶，考虑下面 $d$ 个数

$1,f,f^{2},\cdots,f^{d-1}$

它们都是方程的根，且两两不同余（这是因为若存在 $h'<h<d$ 使得 $f^{h}\equiv f^{h'}$，则 $f^{k}\equiv 1$，其中 $k=h-h'<d$，与阶的定义不符）

根据 Theorem 109，它们是方程的所有根

若 $f^{h}$ 以 $d$ 为阶，那么必须满足 $(h,d)=1$，这是因为若 $k=(h,d)>1$，则

$\left(f^{h}\right)^{d / k}=\left(f^{d}\right)^{h / k} \equiv 1$

即 $f^{h}$ 的阶必将小于 $d$，因此 $h$ 必须在与 $d$ 互质的 $\phi(d)$ 个数中，即 $\psi(d)\leq\phi(d)$，证毕

在定理中取 $d=p-1$，我们得到推论：$p$ 有 $\phi(p-1)$ 个原根

在证明过程中，我们已经证明了下面的定理

Theorem 111
若 $p$ 是奇素数，$g$ 是模 $p$ 的原根，那么
$1,g,g^2,\cdots,g^{p-2}$
两两不同余 $(\bmod p)$

我们知道

$f(x)=x^{p-1}-1$

的根为 $1,2,\cdots,p-1$，结合 Theorem 108 有

Theorem 112
若 $p$ 是素数，那么
$x^{p-1}-1 \equiv(x-1)(x-2) \ldots(x-p+1)(\bmod p)$

比较两边的常数项，我们就能得到威尔逊定理

更一般的，比较 $x,x^{2},\cdots,x^{p-2}$ 项系数，可以得到

Theorem 113
若 $p$ 是奇素数，且 $1\leq l<p-1$，设 $A_{l}$ 表示从集合
$\{1,2,\cdots,p-1\}$
中选出 $l$ 个不同的数的乘积之和，则 $A_{l}\equiv 0(\bmod p)$

我们可以用 Theorem 112 证明 Theorem 76，设

$n=r p-s(r \geqslant 1,0 \leqslant s<p)$

那么有

$\begin{aligned}\binom{p+n-1}{n} &=\frac{(r p-s+p-1) !}{(r p-s) !(p-1) !} \\ &=\frac{(r p-s+1)(r p-s+2) \cdots(r p-s+p-1)}{(p-1) !} \end{aligned}$

设结果为 $i$，根据威尔逊定理，

$(r p-s+1)(r p-s+2) \dots(r p-s+p-1)=(p-1) ! i \equiv-i(\bmod p)$

根据 Theorem 112，左边和下式同余

$(s-1)(s-2) \cdots(s-p+1) \equiv s^{p-1}-1(\bmod p)$

因此

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

当 $p|n$ 时，$s=0$，对应项系数为 $1$，否则，对应项系数为 $0$

---

6、Lagrange's proof of Fermat's and Wilson's theorem(拉格朗日对费马定理与威尔逊定理的证明)

我们对 Theorem 112 的证明是基于费马定理和 Theorem 108

而定理的发现者拉格朗日本人的证明更加简单粗暴，并且他的证明过程中包含了对费马定理及威尔逊定理的证明

我们设 $p$ 是奇素数，则

$(x-1)(x-2) \cdots(x-p+1)=x^{p-1}-A_{1} x^{p-2}+\cdots+A_{p-1}$

其中 $A_{1},A_{2},\ldots$ 的定义与 Theorem 113 中相同，我们两边同乘 $x$，然后把 $x$ 换成 $x-1$ 得到

$\begin{aligned}(x-1)^{p}-A_{1}(x-1)^{p-1}+\cdots+A_{p-1}(x-1)&=(x-1)(x-2) \cdots(x-p) \\&=(x-p)\left(x^{p-1}-A_{1} x^{p-2}+\cdots+A_{p-1}\right) \end{aligned}$

对比各项系数得到

$\begin{aligned}\binom{p}{1}+A_{1}&=p+A_{1} \\ \binom{p}{2}+\binom{p-1}{1}A_{1}+A_{2}&=pA_{1}+A_{2} \\ \binom{p}{3}+\binom{p-1}{2}A_{1}+\binom{p-2}{1}A_{2}+A{3}&=pA_{2}+A_{3}\\ &\cdots\end{aligned}$

第一个式子是恒等式，其余的式子可以化成

$\begin{aligned}A_{1}&=\binom{p}{2} \\ 2A_{2}&=\binom{p}{3}+\binom{p-1}{2}A_{1}\\ 3A_{3}&=\binom{p}{4}+\binom{p-1}{3}A_{1}+\binom{p-2}{2}A_{2}\\ &\cdots\\(p-1)A_{p-1}&=1+A_{1}+A_{2}+\cdots+A_{p-2} \end{aligned}$

因此我们得到

$p\left|A_{1}, \quad p\right| A_{2}, \quad \ldots, \quad p | A_{p-2}$

且

$(p-1) A_{p-1} \equiv 1(\bmod p) \Rightarrow A_{p-1}\equiv -1(\bmod p)$

这就证明了威尔逊定理以及 Theorem 112，费马定理随之得证

---

7、The residue of $\{\frac{1}{2}(p-1)\}!$

设 $p$ 是奇素数，且

$\varpi=\frac{1}{2}(p-1)$

根据威尔逊定理

$\begin{aligned}(p-1) ! &=1.2 \ldots \frac{1}{2}(p-1)\left\{p-\frac{1}{2}(p-1)\right\}\left\{p-\frac{1}{2}(p-3)\right\} \ldots(p-1) \\ & \equiv(-1)^{\varpi}(\varpi !)^{2}(\bmod p) \end{aligned}$

因此

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

当 $p=4n+1$ 时，

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

由于 $-1$ 是模 $p$ 的二次剩余，$\varpi!$ 是方程 $x^2=-1(\bmod p)$ 的某个根

当 $p=4n+3$ 时，

$(\varpi !)^{2} \equiv 1 \Rightarrow \varpi ! \equiv \pm 1(\bmod p)$

由于 $-1$ 是模 $p$ 的二次非剩余，上式中 $\pm 1$ 的取值取决于 $\varpi !$ 是否为模 $p$ 的二次剩余

而 $\varpi !$ 是小于 $\frac{1}{2}p$ 的正整数的乘积，根据 Theorem 85 可得

Theorem 114
若 $p$ 是 $4n+3$ 型素数，那么
$\left\{\frac{1}{2}(p-1)\right\} ! \equiv(-1)^{\nu}(\bmod p)$
其中 $\nu$ 表示小于 $\frac{1}{2}p$ 的二次非剩余的个数

---

8、A theorem of Wolstenholme(沃斯滕霍姆定理)

根据 Theorem 113，我们知道

$1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1}$

的分子能被 $p$ 整除，因为这个分子就是 $A_{p-2}$，更一般的，

Theorem 115
若 $p$ 是大于 $3$ 的素数，那么
$1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1}$
的分子能被 $p^2$ 整除

我们可以用另一种方式来表述这个定理，若 $(i,m)=1$，方程

$i x \equiv 1(\bmod m)$

仅有一个根 $x$，且 $i,x$ 互为数论共轭，这对数论共轭比较特殊，它们的乘积是 $1$，我们称这样的数论共轭为乘法逆元，记作

$\frac{1}{i}=\overline{i}$

更一般的，我们用 $\frac{a}{b}$ 表示方程 $ax\equiv b(\bmod m)$ 的根

引入这样的记号后，我们就得到了 Wolstenholme's theorem，

Theorem 116（Wolstenholme's Theorem）
若 $p>3$，且 $\frac{1}{i}$ 表示 $i$ 的乘法逆元 $(\bmod p^{2})$，那么
$1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1} \equiv 0\left(\bmod p^{2}\right)$

为了解释乘法逆元符号的应用，我们先来证明

$1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1} \equiv 0\left(\bmod p\right)$

我们知道，对于 $0<i<p$，有

$i \cdot \frac{1}{i} \equiv 1, \quad(p-i) \frac{1}{p-i} \equiv 1(\bmod p)$

因此

$i\left(\frac{1}{i}+\frac{1}{p-i}\right) \equiv i \cdot \frac{1}{i}-(p-i) \frac{1}{p-i} \equiv 0(\bmod p)$

$\frac{1}{i}+\frac{1}{p-i} \equiv 0(\bmod p)$

然后我们求个和就能证明这个问题了

接下来我们来说明一下 Theorem 115 和 Theorem 116 是等价的

对于 $0<x<p$，设 $\overline{x}$ 表示 $x$ 的乘法逆元 $(\bmod p^{2})$，那么

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

因此

$\begin{array}{l}{(p-1) !(\overline{1}+\overline{2}+\cdots+\overline{p-1})} \\ {\quad \equiv(p-1) !\left(1+\frac{1}{2}+\cdots+\frac{1}{p-1}\right)\left(\bmod p^{2}\right)}\end{array}$

等式右边就是分子，等价性即证，接下来证明这个定理

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

令 $x=p$，得到

$(p-1) !=p^{p-1}-A_{1} p^{p-2}+\ldots-A_{p-2} p+A_{p-1}$

我们知道 $(p-1)!=A_{p-1}$，因此

$p^{p-2}-A_{1} p^{p-3}+\ldots+A_{p-3 p}-A_{p-2}=0$

由于 $p>3$ 且 $p\left|A_{1}, p\right| A_{2}, \ldots, p | A_{p-3}$，得到 $p^{2} | A_{p-2}$，即

$p^{2} |(p-1) !\left(1+\frac{1}{2}+\ldots+\frac{1}{p-1}\right)$

证毕，另外还有一个定理

Theorem 117
若 $p>3$，那么
$C_{p}=1+\frac{1}{2^{2}}+\ldots+\frac{1}{(p-1)^{2}}\equiv 0(\bmod p)$

事实上，$C_{p}$ 的分子就是 $A_{p-2}^{2}-2 A_{p-1} A_{p-3}$，显然成立

---

9、The theorem of von Staudt(施陶特定理)

我们最后介绍施陶特定理，这个定理与 Bernoulli's number(伯努利数) 有关

伯努利数通常定义为

$\frac{x}{e^{x}-1}=1-\frac{1}{2} x+\frac{B_{1}}{2 !} x^{2}-\frac{B_{2}}{4 !} x^{4}+\frac{B_{3}}{6 !} x^{6}-\dots$

该展开式在 $|x|<2\pi$ 时收敛，我们发现，另外一种写法更为简洁

$\frac{x}{e^{x}-1}=\beta_{0}+\frac{\beta_{1}}{1 !} x+\frac{\beta_{2}}{2 !} x^{2}+\frac{\beta_{3}}{3 !} x^{3}+\ldots$

其中 $\beta_{0}=1, \beta_{1}=-\frac{1}{2}$，且

$\beta_{2 k}=(-1)^{k-1} B_{k}, \quad \beta_{2 k+1}=0 \quad(k \geqslant 1)$

伯努利数与 $\sum m^k$ 的 Euler-Maclaurin sum-formula(欧拉-麦克劳林求和公式) 密切相关，事实上，

$1^{k}+2^{k}+\ldots+(n-1)^{k}=\sum_{r=0}^{k} \frac{1}{k+1-r}\binom{k}{r} n^{k+1-r} \beta_{r}$

这是因为左边的式子是

$k ! x\left(1+e^{x}+e^{2 x}+\ldots+e^{(n-1) x}\right)$

中 $x^{k+1}$ 项系数，而

$\begin{array}{l}{k! x\left(1+e^{x}+e^{2 x}+\ldots+e^{(n-1) x}\right)} \\ {\quad=k ! x \frac{1-e^{n x}}{1-e^{x}}=k ! \frac{x}{e^{x}-1}\left(e^{n x}-1\right)} \\ {\quad=k !\left(1+\frac{\beta_{1}}{1 !} x+\frac{\beta_{2}}{2 !} x^{2}+\cdots\right)\left(nx+\frac{n^{2} x^{2}}{2 !}+\ldots\right)}\end{array}$

计算对应的 $x^{k+1}$ 系数就得到了上面的结论

施陶特定理基于 $B_{k}$ 的小数部分

Theorem 118（Staudt's Theorem）
若 $k\geq 1$，那么
$(-1)^{k} B_{k} \equiv \sum_{(p-1)|2k} \frac{1}{p}(\bmod 1)$

例如，若 $k=1$，那么和式中 $p=2,3$，而 $B_{1}=-\frac{5}{6}$，显然成立

我们把 $B_{k}$ 换成 $\beta_{k}$，即

$\beta_{k}+\sum_{(p-1) | k} \frac{1}{p}=i$

其中 $k=1,2,4,6,\ldots$，且 $i$ 是一个整数，如果定义 $\epsilon_{k}(p)$ 为

$\epsilon_{k}(p)=\left\{\begin{matrix}1,&(p-1) \mid k \\ 0,&(p-1) \nmid k\end{matrix}\right.$

那么式子就可以写成

$\beta_{k}+\sum \frac{\epsilon_{k}(p)}{p}=i$

事实上，施陶特定理说明了伯努利数的分母中没有平方因子

---

10、Proof of von Staudt's theorem(施陶特定理的证明)

我们首先来证明一个引理

Theorem 119
$\sum_{m=1}^{p-1} m^{k} \equiv-\epsilon_{k}(p)(\bmod p)$

若 $(p-1)\mid k$，那么根据费马定理，$m^k\equiv 1(\bmod p)$，因此

$\sum m^{k} \equiv p-1 \equiv-1 \equiv-\epsilon_{k}(p)(\bmod p)$

若 $(p-1)\nmid k$，设 $g$ 是模 $p$ 的原根，那么根据 Theorem 88，

$g^{k} \not\equiv 1(\bmod p)$

由于集合 $\{g,2g,\ldots,(p-1)g\}$ 与 $\{1,2,\ldots,p-1\}$ 同余 $(\bmod p)$

$\sum(m g)^{k} \equiv \sum m^{k}\Rightarrow \left(g^{k}-1\right) \sum m^{k} \equiv 0(\bmod p)$

这样就得到了

$\sum m^{k} \equiv 0=-\epsilon_{k}(p)(\bmod p)$

现在我们用数学归纳法来证明 Theorem 118

我们知道定理中 $k=1,2,4,6,\ldots$，显然当 $k=1,2$ 时定理成立

假设定理在 $L=\{1,2,4,\ldots,k-2\}$ 的范围内成立，我们需要证明定理对于 $k$ 成立

设 $\varpi$ 是任意素数，根据 Theorem 119

$\epsilon_{k}(\varpi)+\sum_{r=0}^{k} \frac{1}{k+1-r}\binom{k}{r} \varpi^{k+1-r} \beta_{r} \equiv 0(\bmod \varpi)$

由于 $\beta_{k-1}=0$，得到

$\beta_{k}+\frac{\epsilon_{k}(\varpi)}{\varpi}+\sum_{r=0}^{k-2} \frac{1}{k+1-r}\binom{k}{r} \varpi^{k-1-r}\left(\varpi \beta_{r}\right) \equiv 0(\bmod 1)$

接下来我们考虑

$u_{k, r}=\frac{1}{k+1-r}\binom{k}{r} \varpi^{k-1-r}\left(\varpi \beta_{r}\right)$

的分母能否被 $\varpi$ 整除

若 $r\not\in L$，则 $\beta_{r}=1或0$，否则根据归纳假设，$\beta_{r}$ 的分母中不含平方因子，即 $(\varpi \beta_{r})$ 的分母不能被 $\varpi$ 整除，而 $\binom{k}{r}$ 是整数，因此 $u_{k,r}$ 的分母能被 $\varpi$ 整除当且仅当

$\frac{\varpi^{k-1-r}}{k+1-r}=\frac{\varpi^{s-1}}{s+1}$

的分母能被 $\varpi$ 整除，那就需要满足

$s+1 \geqslant \varpi^{s}$

但是我们知道 $s=k-r\geq 2$，因此

$s+1<2^{s} \leqslant \varpi^{s}$

所以 $u_{k,r}$ 的分母不能被 $\varpi$ 整除，故

$\beta_{k}+\frac{\epsilon_{k}(\varpi)}{\varpi}=\frac{a_{k}}{b_{k}}$

其中 $\varpi\nmid b_{k}$，且

$\frac{\epsilon_{k}(p)}{p}(p \neq \varpi)$

显然有相同的形式，故

$\beta_{k}+\sum \frac{\epsilon_{k}(p)}{p}=\frac{A_{k}}{B_{k}}$

其中 $B_{k}\nmid \varpi$，由于 $\varpi$ 是任意素数，所以 $B_{k}=1$，证毕

特别的，若 $k$ 是 $3n+1$ 型素数，那么在 $(p-1)|2k$ 条件下

$p=2,3,k+1,2k+1$

但是 $k+1$ 是偶数，$2k+1=6n+3$ 不是素数，因此 $p=2,3$，故

Theorem 120
若 $k$ 是 $3n+1$ 型素数，那么
$B_{k}\equiv \frac{1}{6}(\bmod 1)$

事实上，这个定理可以推广到对于给定的 $k$，有无穷多个 $B_{l}$ 使得

$B_{l}\equiv B_{k}(\bmod 1)$

我们需要 Dirichlets 的 Theorem 15 来证明它