第八章 模合数意义下的同余

---

1、Linear congruences(线性同余方程)

在之前的章节中，我们考虑的大多是模数为素数的同余式，本章我们将考虑一些一般模数下的理论，当模数是合数时，这些理论要复杂得多

我们考虑第五章中的线性同余方程

$ax\equiv b(\bmod m)$

回想一下之前证明的结论，该方程有解当且仅当

$d=(a,m)|b$

且有解时仅有 $d$ 个解，分别为

$\xi, \xi+\frac{m}{d}, \xi+2 \frac{m}{d}, \ldots, \xi+(d-1) \frac{m}{d}$

其中 $\xi$ 是下面方程的唯一解

$\frac{a}{d} x \equiv \frac{b}{d}\left(\bmod \frac{m}{d}\right)$

接下来考虑同余方程组

$\left\{\begin{matrix}a_{1}x\equiv b_{1} &(\bmod m_{1}) \\ a_{2}x\equiv b_{2} &(\bmod m_{2}) \\ \cdots \\ a_{k}x\equiv b_{k} &(\bmod m_{k}) \end{matrix}\right.$

其中，模数 $m_{1},m_{2},\ldots,m_{k}$ 互质，方程组有解当且仅当所有的方程满足

$(a_{i},m_{i})|b_{i}$

如果方程组有解，那么可以解出每个方程，问题简化为了同余方程组

$\left\{\begin{matrix}x\equiv c_{1} &(\bmod m_{1}) \\ x\equiv c_{2} &(\bmod m_{2}) \\ \cdots \\ x\equiv c_{k} &(\bmod m_{k}) \end{matrix}\right.$

这个方程组中的模数与之前的不同，事实上新的 $m_{i}$ 等于原先的 $\frac{m_{i}}{(a_{i},m_{i})}$，记

$m=m_{1} m_{2} \cdots m_{k}=m_{1} M_{1}=m_{2} M_{2}=\cdots=m_{k} M_{k}$

由于 $(m_{i},M_{i})$ 互质，存在唯一的 $n_{i}$ 使得

$n_{i} M_{i} \equiv 1\left(\bmod m_{i}\right)$

这里的 $n_{i}$ 就是 $M_{i}$ 模 $m_{i}$ 的乘法逆元，取

$x=n_{1} M_{1} c_{1}+n_{2} M_{2} c_{2}+\cdots+n_{k} M_{k} c_{k}$

那么对于每一个方程，有

$x \equiv n_{i} M_{i} c_{i} \equiv c_{i}\left(\bmod m_{i}\right)$

因此 $x$ 满足方程组，假设另有一解 $y$ 满足

$y \equiv c_{i} \equiv x\left(\bmod m_{i}\right)$

由于所有的 $m_{i}$ 互质，有

$y \equiv x(\bmod m)$

因此 $x$ 是方程组的唯一解 $(\bmod m)$

Theorem 121（中国剩余定理）
若 $m_{1}, m_{2}, \dots, m_{k}$ 互质，那么同余方程组
$\left\{\begin{matrix}x\equiv c_{1} &(\bmod m_{1}) \\ x\equiv c_{2} &(\bmod m_{2}) \\ \cdots \\ x\equiv c_{k} &(\bmod m_{k}) \end{matrix}\right.$
有唯一解 $(\bmod m)$
$x=n_{1} M_{1} c_{1}+n_{2} M_{2} c_{2}+\cdots+n_{k} M_{k} c_{k}$
其中 $m=\Pi_{i=1}^{k}m_{i}，M_{i}=\frac{m}{m_{i}}，n_{i}\equiv M_{i}^{-1}(\bmod m_{i})$

---

2、Congruences of higher degree(高次同余方程)

我们现在考虑一般的高次同余方程

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

其中，$f(x)$ 是整系数多项式，我们把方程分解为若干个同余方程，这些方程的模数是素数的整次幂，设

$m=m_{1} m_{2} \ldots m_{k}$

其中所有的 $m_{i}$ 互质，那么原方程的每一个解都满足

$f(x) \equiv 0\left(\bmod m_{i}\right) \quad(i=1,2, \ldots, k)$

设 $c_{1},c_{2},\dots,c_{k}$ 是这些方程的一组解，$x$ 是方程组

$x \equiv c_{i}\left(\bmod m_{i}\right) \quad(i=1,2, \ldots, k)$

的解（由 Theorem 121 求出），那么

$f(x) \equiv f\left(c_{i}\right) \equiv 0\left(\bmod m_{i}\right)\Rightarrow f(x) \equiv 0(\bmod m)$

因此每一组解 $c_{1},c_{2},\dots,c_{k}$ 对应了原方程的一个解

Theorem 122
高次同余方程
$f(x) \equiv 0(\bmod m)$
根的个数等于下面这些方程
$f(x) \equiv 0\left(\bmod m_{i}\right) \quad(i=1,2, \ldots, k)$
根的个数的乘积

若 $m=p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{k}^{a_{k}}$，我们可以取 $m_{i}=p_{i}^{a_{i}}$

---

3、Congruences to a prime-power modulus(模素数幂下的同余方程)

现在我们考虑方程

$f(x) \equiv 0\left(\bmod p^{a}\right)\tag{8.3.1}$

其中 $p$ 是素数，且 $a>1$，设 $x$ 是方程的一个根且 $0\leq x<p^{a}$，那么

$f(x) \equiv 0\left(\bmod p^{a-1}\right)\tag{8.3.2}$

因此 $x$ 有

$x=\xi+s p^{a-1}(0 \leqslant s<p)\tag{8.3.3}$

的形式，其中 $\xi$ 是 $(8.3.2)$ 的根，且 $0 \leqslant \xi<p^{a-1}$

接下来使用泰勒公式进行展开

$\begin{aligned} f\left(\xi+s p^{a-1}\right) &=f(\xi)+s p^{a-1} f^{\prime}(\xi)+\frac{1}{2} s^{2} p^{2 a-2} f^{\prime \prime}(\xi)+\cdots \\ & \equiv f(\xi)+s p^{a-1} f^{\prime}(\xi)\left(\bmod p^{a}\right) \end{aligned}$

其中 $a\geq 2$，故

$2 a-2 \geqslant a, 3 a-3 \geqslant a, \dots$

且系数 $\frac{f^{(k)}(\xi)}{k !}$ 是整数，因此后面的项都是 $p^{a}$ 的倍数，接下来分两种情况讨论

（1）若

$f^{\prime}(\xi) \not\equiv 0(\bmod p)$

那么 $\xi+sp^{a-1}$ 是 $(8.3.1)$ 的根当且仅当

$f(\xi)+s p^{a-1} f^{\prime}(\xi) \equiv 0\left(\bmod p^{a}\right)$

$s f^{\prime}(\xi) \equiv-\frac{f(\xi)}{p^{a-1}}(\bmod p)$

仅有一个 $s$ 满足条件，因此 $(8.3.1)$ 与 $(8.3.2)$ 有相同数量的根

（2）若

$f^{\prime}(\xi) \equiv 0(\bmod p)$

那么

$f\left(\xi+s p^{a-1}\right) \equiv f(\xi)\left(\bmod p^{a}\right)$

若 $f(\xi) \not\equiv 0\left(\bmod p^{a}\right)$，则 $(8.3.1)$ 无对应根

若 $f(\xi) \equiv 0\left(\bmod p^{a}\right)$，那么对于所有的 $s$，$(8.3.3)$ 都是 $(8.3.1)$ 的根

Theorem 123
设 $\xi$ 是高次同余方程
$f(x) \equiv 0\left(\bmod p^{a-1}\right)$
的一个根，那么高次同余方程
$f(x) \equiv 0\left(\bmod p^{a}\right)$
的根与 $\xi$ 的关系如下：
（1）若 $f^{\prime}(\xi) \equiv 0(\bmod p)$ 且 $\xi$ 不是方程的根，则 $\xi$ 没有对应方程的根
（2）若 $f^{\prime}(\xi) \not\equiv 0(\bmod p)$，则 $\xi$ 对应了方程的一个根
（3）若 $f^{\prime}(\xi) \equiv 0(\bmod p)$ 且 $\xi$ 是方程的根，则 $\xi$ 对应了方程的 $p$ 个根

现在我们求出了 $(8.3.1)$ 与 $(8.3.2)$ 的关系，成功地将模数降次解决了问题

---

4、Examples(例子)

（1）我们知道同余方程

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

有 $p-1$ 个根 $1,2,\ldots,p-1$，若 $\xi$ 是其中一根，则

$f^{\prime}(\xi)=(p-1) \xi^{p-2} \not\equiv 0(\bmod p)$

因此，方程

$f(x) \equiv 0(\bmod p^{2})$

有 $p-1$ 个根，进一步的有下面的定理

Theorem 124
对于任意的 $a\geq 1$，高次同余方程
$x^{p-1}-1 \equiv 0\left(\bmod p^{a}\right)$
有且仅有 $p-1$ 个根

（2）我们考虑同余方程

$f(x)=x^{\frac{1}{2} p(p-1)}-1 \equiv 0(\bmod p^{2})\tag{8.4.1}$

其中 $p$ 是奇素数，这里对于任意的 $\xi$，有

$f^{\prime}(\xi)=\frac{1}{2} p(p-1) \xi^{\frac{1}{2} p(p-1)-1} \equiv 0(\bmod p)$

因此，方程

$f(x)\equiv 0(\bmod p)\tag{8.4.2}$

的每一个根 $\xi$ 都对应了 $(8.4.1)$ 的 $p$ 个根，根据 Theorem 83

$x^{\frac{1}{2}(p-1)} \equiv \pm 1(\bmod p)$

正负号取决于 $x$ 是否为模 $p$ 的二次剩余，且

$x^{\frac{1}{2} p(p-1)} \equiv \pm 1(\bmod p)$

也是一样的，因此 $(8.4.2)$ 有 $\frac{1}{2}(p-1)$ 个根，$(8.4.1)$ 有 $\frac{1}{2}p(p-1)$ 个根

我们在第六章中定义了模素数下的二次剩余，类似的，我们定义模 $p^2$ 下的二次剩余

若 $(x,p)=1$ 且存在 $y$ 使得 $y^{2} \equiv x\left(\bmod p^{2}\right)$，那么 $x$ 是模 $p^2$ 的二次剩余

若 $(x,p)=1$ 且不存在 $y$ 使得 $y^{2} \equiv x\left(\bmod p^{2}\right)$，那么 $x$ 是模 $p^2$ 的二次非剩余

根据定义，若 $x$ 是模 $p^2$ 的二次剩余，则根据 Theorem 72

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

因此 $x$ 是 $(8.4.1)$ 的一根

另一方面，模 $p^{2}$ 的简化剩余系中有 $p(p-1)$ 个数，若 $y_{1},y_{2}$ 是其中的两个数且

$y_{1}^{2} \equiv y_{2}^{2}(\bmod p^{2})\Rightarrow p^{2}|(y_{1}+y_{2})(y_{1}-y_{2})$

由于 $p|(y_{1}+y_{2})$ 和 $p|(y_{1}-y_{2})$ 不能同时成立，因此

$y_{1}+y_{2}=p^{2}$

因此，模 $p^{2}$ 的简化剩余系中有 $\frac{1}{2}p(p-1)$ 个数 $y$，使得 $y^{2}$ 两两不同余

故模 $p^{2}$ 下有 $\frac{1}{2}p(p-1)$ 个二次剩余，它们对应了 $(8.4.1)$ 的根

Theorem 125
模 $p^{2}$ 下有 $\frac{1}{2}p(p-1)$ 个二次剩余，它们对应了方程
$x^{\frac{1}{2} p(p-1)}-1 \equiv 0(\bmod p^{2})$
的 $\frac{1}{2}p(p-1)$ 个根

（3）我们最后考虑同余方程

$f(x)=x^{2}-c \equiv 0\left(\bmod p^{a}\right)\tag{8.4.3}$

其中 $p\nmid c$ 且 $p$ 是奇素数，那么对于 $\xi\not\equiv 0(\bmod p)$，有

$f^{\prime}(\xi)=2 \xi \not\equiv 0(\bmod p)$

因此 $(8.4.3)$ 的根的数量与模数为 $p^{a-1}, p^{a-2}, \dots, p$ 时相同

也就是说 $(8.4.3)$ 无解或有两个根取决于 $c$ 是否为模 $p$ 的二次剩余

当 $p=2$ 时情况更为复杂，因为此时，对于任意的 $\xi$

$f^{\prime}(\xi)=2 \xi \equiv 0(\bmod p)$

我们的结论是当 $a=2$ 时，方程有 $2$ 根或无解，当 $a\geq 3$ 时，方程有 $4$ 根或无解

---

5、Bauer's identical congruence(鲍尔同余方程)

设 $t(m)$ 表示与 $m$ 互质且小于 $m$ 的 $\phi(m)$ 个数的集合，记

$f_{m}(x)=\prod_{t\in t(m)}(x-t)\tag{8.5.1}$

当 $m$ 是素数时，根据 Theorem 112，

$f_{m}(x)=x^{\phi(m)}-1(\bmod m)\tag{8.5.2}$

由于

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

总有 $\phi(m)$ 个根 $t$，所以我们期望 $(8.5.2)$ 对于所有的 $m$ 成立

然而这个猜想并不正确，例如，当 $m=9$ 时，$t=\pm 1,\pm 2,\pm 4(\bmod 9)$，有

$f_{m}(x) \equiv\left(x^{2}-1^{2}\right)\left(x^{2}-2^{2}\right)\left(x^{2}-4^{2}\right)\equiv x^{6}-3 x^{4}+3 x^{2}-1(\bmod 9)$

正确的结论来自 Bauer(鲍尔)，包含下面两条定理

Theorem 126
若 $p$ 是 $m$ 的奇质因子，且 $p^a$ 是 $m$ 的质因子分解式中因子 $p$ 的最高次项，那么
$f_{m}(x)=\prod_{t\in t(m)}(x-t) \equiv\left(x^{p-1}-1\right)^{\phi(m) /(p-1)}\left(\bmod p^{a}\right)\tag{8.5.3}$
特别的，
$f_{p^{a}}(x)=\prod_{t\in t\left(p^{a}\right)}(x-t) \equiv\left(x^{p-1}-1\right)^{p^{a-1}}\left(\bmod p^{a}\right)\tag{8.5.4}$

Theorem 127
若 $m>2$ 是偶数，且 $2^a$ 是 $m$ 的质因子分解式中因子 $2$ 的最高次项，那么
$f_{m}(x) \equiv\left(x^{2}-1\right)^{\frac{1}{2} \phi(m)}\left(\bmod 2^{a}\right)\tag{8.5.5}$
特别的，
$f_{2^a} (x) \equiv\left(x^{2}-1\right)^{2^{a-2}}\left(\bmod 2^{a}\right)\tag{8.5.6}$

注：当 $m=2$ 时，$f_{2}(x)=x-1$，这种情况满足 $(8.5.3)$ 而不满足 $(8.5.5)$

我们先来证明 $(8.5.4)$，使用数学归纳法

当 $a=1$ 时，显然成立

当 $a>1$ 时，集合 $t(p^a)$ 中的数为

$t+v p^{a-1}(0 \leqslant v<p),\quad t\in t(p^{a-1})$

因此

$\begin{aligned}f_{p^{a}}(x)&=\prod_{t\in t\left(p^{a}\right)}\prod_{v=0}^{p-1}(x-t-vp^{a-1}) \\ &=\prod_{v=0}^{p-1}\prod_{t\in t\left(p^{a}\right)}\{(x-vp^{a-1})-t\} =\prod_{v=0}^{p-1} f_{p^{a-1}}\left(x-v p^{a-1}\right)\end{aligned}$

由泰勒展开得到，

$f_{p^{a-1}}\left(x-v p^{a-1}\right) \equiv f_{p^{a-1}}(x)-v p^{a-1} f_{p^{a-1}}^{\prime}(x)\left(\bmod p^{a}\right)$

因此

$\begin{aligned} f_{p^{a}}(x) & \equiv\left\{f_{p^{a-1}}(x)\right\}^{p}-\sum_{v=0}^{p-1} v \cdot p^{a-1}\left\{f_{p^{a-1}}(x)\right\}^{p-1} f_{p^{a-1}}^{\prime}(x) \\ & \equiv\left\{f_{p^{a-1}}(x)\right\}^{p}\left(\bmod p^{a}\right) \end{aligned}$

这样我们就证明了 $(8.5.4)$，接下来证明 $(8.5.3)$

设 $m=p^{a}M$ 且 $p^{a}\nmid M$，$t$ 取遍 $t(p^{a})$ 中的所有 $\phi(p^{a})$ 个值，$T$ 取遍 $t(M)$ 中的所有 $\phi(M)$ 个值，根据 Theorem 61，

$t M+T p^{a}$

取遍 $t(m)$ 中的所有 $\phi(m)$ 个值，因此

$f_{m}(x)=\prod_{t\in t(m)}(x-t) \equiv \prod_{T \in t(M)} \prod_{t \in t\left(p^{a}\right)}\left(x-t M-T p^{a}\right)(\bmod m)$

对于每一个的 $T$，$(p^{a},M)=1$，因此

$\begin{aligned} \prod_{t \in t\left(p^{a}\right)}\left(x-t M-T p^{a}\right) & \equiv \prod_{t \in t\left(p^{a}\right)}(x-t M) \\ & \equiv \prod_{t \in t\left(p^{a}\right)}(x-t) \equiv f_{p^{a}}(x)\left(\bmod p^{a}\right) \end{aligned}$

由于 $t(M)$ 中有 $\phi(M)$ 个数，根据 $(8.5.4)$，

$f_{m}(x) \equiv\left(x^{p-1}-1\right)^{p^{a-1} \phi(M)}\left(\bmod p^{a}\right)$

其中

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

这样就证明了 $(8.5.3)$

接下来考虑 $p=2$ 的特殊情况，我们还是用数学归纳法证明 $(8.5.6)$

当 $a=2$ 时成立，因为

$f_{4}(x)=(x-1)(x-3) \equiv x^{2}-1(\bmod 4)$

当 $a>2$ 时，设

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

则有

$f_{2^{a-1}}^{\prime}(x) \equiv 0(\bmod 2)$

因此

$\begin{aligned} f_{2^{a}}(x) &=f_{2^{a-1}}(x) f_{2^{a-1}}\left(x-2^{a-1}\right) \\ & \equiv\left\{f_{2^{a-1}}(x)\right\}^{2}-2^{a-1} f_{2^{a-1}}(x) f_{2^{a-1}}^{\prime}(x) \\ & \equiv\left\{f_{2^{a-1}}(x)\right\}^{2} \equiv\left(x^{2}-1\right)^{2^{a-2}}\left(\bmod 2^{a}\right) \end{aligned}$

证明完毕，接下来推广到 $(8.5.5)$，需要分两种情况讨论

（1）若 $m=2M$，$M$ 是大于 $1$ 的奇数，那么

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

这是因为 $(x-1)^{2} \equiv x^{2}-1(\bmod 2)$

（2）若 $m=2^{a}M$，$M$ 是奇数且 $a>1$，这种情况下的证明和上面类似

设 $t$ 取遍 $t(2^{a})$ 中的值，$T$ 取遍 $t(M)$ 中的值，根据 Theorem 61，

$t M+T 2^{a}$

取遍 $t(m)$ 中的值，因此

$\begin{aligned} f_{m}(x) &=\prod_{t\in t(m)}(x-t) \equiv \prod_{T \in t(M)} \prod_{t \in t\left(2^{a}\right)}\left(x-t M-2^{a} T\right)(\bmod m) \\ & \equiv\left\{f_{2^a}(x)\right\}^{\phi(M)}(\bmod 2^{a}) \equiv (x^2-1)^{2^{a-2}\phi(M)}\end{aligned}$

其中

$2^{a-2}\phi(M)=\frac{\phi(2^{a})\phi(M)}{2}=\frac{1}{2}\phi(m)$

证明完毕

---

6、A theorem of Leudesdorf(勒得斯道夫定理)

我们可以用 Bauer 定理推广 Wolstenholme's Theorem 115

Theorem 128
设
$S_{m}=\sum_{t\in t(m)} \frac{1}{t}$
若 $2\nmid m,3\nmid m$，则
$S_{m} \equiv 0\left(\bmod m^{2}\right)\tag{8.7.1}$
若 $2\nmid m,3\mid m$，则
$S_{m} \equiv 0\left(\bmod \frac{1}{3} m^{2}\right)\tag{8.7.2}$
若 $2\mid m,3\nmid m$，且 $m$ 不是 $2$ 的整次幂，则
$S_{m} \equiv 0\left(\bmod \frac{1}{2} m^{2}\right)\tag{8.7.3}$
若 $2\mid m,3\mid m$，则
$S_{m} \equiv 0\left(\bmod \frac{1}{6} m^{2}\right)\tag{8.7.4}$
若 $m=2^{a}$，则
$S_{m} \equiv 0\left(\bmod \frac{1}{4} m^{2}\right)\tag{8.7.5}$

为了公式书写方便，我们约定在下面的证明过程中

$\sum,\prod,\sum^{\prime},\prod^{\prime} 表示 \sum_{t\in t(m)},\prod_{t\in t(m)},\sum_{t\in t(m),t<\frac{1}{2}m},\prod_{t\in t(m),t<\frac{1}{2}m}$

我们考虑 $m$ 的每一个质因子 $p$，若 $p>2$，根据 Theorem 126，

$\begin{aligned}\left(x^{p-1}-1\right)^{\phi(m) /(p-1)} & \equiv \prod(x-t)=\prod^{\prime}(x-t)(x-m+t) \\ & \equiv \prod^{\prime}\left\{x^{2}+t(m-t)\right\}\left(\bmod p^{a}\right) \end{aligned}\tag{8.7.6}$

比较两边 $x^2$ 项系数，若 $p>3$，左边系数为 $0$，则

$\begin{aligned}0 &\equiv \prod^{\prime} t(m-t) \sum^{\prime} \frac{1}{t(m-t)}=\frac{1}{2} \prod t \sum \frac{1}{t(m-t)}\left(\bmod p^{a}\right)\end{aligned}\tag{8.7.7}$

因此

$\begin{aligned} S_{m} \prod t &=\prod t \sum \frac{1}{t}=\frac{1}{2} \prod t \sum\left(\frac{1}{t}+\frac{1}{m-t}\right) \\ &=\frac{1}{2} m \prod t \sum \frac{1}{t(m-t)} \equiv 0\left(\bmod p^{2 a}\right) \end{aligned}$

因此

$S_{m}\equiv 0(\bmod p^{2a})\tag{8.7.8}$

若 $2\nmid m,3\nmid m$，则对 $m$ 的所有质因子 $p$ 使用中国剩余定理合并得到 $(8.7.1)$

若 $p=3$，那么 $(8.7.7)$ 就变成了

$(-1)^{\frac{1}{2} \phi(m)-1} \frac{1}{2} \phi(m) \equiv \frac{1}{2} \prod t \sum \frac{1}{t(m-t)}\left(\bmod 3^{a}\right)$

因此

$S_{m} \prod t \equiv(-1)^{\frac{1}{2} \phi(m)-1} \frac{1}{2} m \phi(m)\left(\bmod 3^{2 a}\right)$

由于 $\phi(m)$ 是偶数，且 $3^{a-1}|\phi(m)$，因此

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

中国剩余定理合并之后得到 $(8.7.2)$

若 $p=2$，那么根据 Theorem 127，

$\left(x^{2}-1\right)^{\frac{1}{2} \phi(m)} \equiv \prod^{\prime}\left\{x^{2}+t(m-t)\right\}\left(\bmod 2^{a}\right)$

因此

$(-1)^{\frac{1}{2} \phi(m)-1} \frac{1}{2} \phi(m) \equiv \frac{1}{2} \prod t \sum \frac{1}{t(m-t)}$

$S_{m} \prod t=\frac{1}{2} m \prod t \sum \frac{1}{t(m-t)} \equiv(-1)^{\frac{1}{2} \phi(m)-1} \frac{1}{2} m \phi(m)\left(\bmod 2^{2 a}\right)$

设 $m=2^{a}M$，其中 $M$ 是大于 $1$ 的奇数，那么

$\frac{1}{2} \phi(m)=2^{a-2} \phi(M)$

能被 $2^{a-1}$ 整除，因此

$S_{m} \equiv 0\left(\bmod 2^{2 a-1}\right)$

结合之前得到的结果可以推出 $(8.7.3),(8.7.4)$

最后，若 $m=2^{a}$，则 $\frac{1}{2} \phi(m)=2^{a-2}$，因此

$S_{m} \equiv 0\left(\bmod 2^{2 a-2}\right)$

即 $(8.7.5)$

---

7、Further consequences of Bauer's theorem(鲍尔定理的更多结论)

（1）设

$m>2, \quad m=\prod p^{a}, \quad u_{2}=\frac{1}{2} \phi(m), \quad u_{p}=\frac{\phi(m)}{p-1}(p>2)$

那么 $\phi(m)$ 是偶数，且当我们比较等式 $(8.5.3)$ 两边的常数项以及 $(8.5.5)$ 两边的常数项时，我们可以得到

$\prod_{t\in t(m)} t \equiv(-1)^{u_{p}}\left(\bmod p^{a}\right)$

• 当 $m\neq 4,p^{a},2p^{a}$ 时， $u_{2},u_{p}$ 都是偶数，从而 $\Pi t \equiv 1(\bmod m)$

• 当 $m=4$ 时，$\Pi t=1\times 3 \equiv-1(\bmod 4)$

• 当 $m=p^{a},2p^{a}$ 时，$u_{p}$ 是偶数，$\Pi t=-1(\bmod m)$

Theorem 129
$\prod_{t\in t(m)} t \equiv \left\{\begin{matrix}+1, & m\neq 4,p^{a},2p^{a}\\ -1 ,& m= 4,p^{a},2p^{a}\end{matrix}\right. (\bmod m)$

特别的，当 $m=p$ 时，得到威尔逊定理

（2）设 $p>2$ 且

$f(x)=\prod_{t\in t\left(p^{a}\right)}(x-t)=x^{\phi\left(p^{a}\right)}-A_{1} x^{\phi\left(p^{a}\right)-1}+\cdots$

我们发现 $f(x)$ 有对称轴 $x=\frac{1}{2}p^{a}$，因此

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

结合泰勒展开式有

$\begin{aligned} 2 A_{1} x^{\phi\left(p^{a}\right)-1}+2 A_{3} x^{\phi\left(p^{a}\right)-3}+\cdots &=f(-x)-f(x)=f\left(p^{a}+x\right)-f(x) \\ & \equiv p^{a} f^{\prime}(x)\left(\bmod p^{2 a}\right) \end{aligned}$

根据 Theorem 126，我们有

$\begin{aligned}p^{a} f^{\prime}(x)&=p^{a}\{(x^{p-1}-1)^{p^{a}-1}\}^{\prime} \\ &\equiv p^{2 a-1}(p-1) x^{p-2}\left(x^{p-1}-1\right)^{p^{a-1}-1}\\ &\equiv -p^{2a-1}x^{p-2}\left(x^{p-1}-1\right)^{p^{a-1}-1}\left(\bmod p^{2 a}\right)\end{aligned}$

由于 $\phi(p)|(p^{a-1}-1)$，得到

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

因此

$p^{a} f^{\prime}(x)\equiv -p^{2a-1}x^{p-2}(kp+1)\equiv -p^{2a-1}x^{p-2}(\bmod p^{2a})$

对比两边系数我们发现除了 $x^{p-2}$ 项，其它项系数

$A_{2\nu+1}\equiv 0(\bmod p^{2a})$

考虑 $x^{p-2}$ 项，此时指数满足

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

得到

$2\nu \equiv 0 (\bmod p-1)$

Theorem 130
若 $A_{2\nu+1}$ 是 homogeneous product(齐次项) 之和（在 Theorem 113 中定义），$2\nu+1\in t(p^{a})$ 且 $(p-1)\nmid 2\nu$，则
$A_{2 v+1} \equiv 0\left(\bmod p^{2 a}\right)$

$a=1, \quad 2 \nu+1=p-2, \quad p>3$

的情况就是 Wolstenholme's theorem

（3）这里还有一个有趣的定理研究和式

$S_{2 \nu+1}=\sum_{t\in t(p)} \frac{1}{t^{2 \nu+1}}$

此时，根据 Theorem 112，

$f(x)=\prod_{t\in t\left(p\right)}(x-t)=x^{p-1}-1$

根据乘积的链式求导法，有

$\frac{f^{\prime}(x)}{f(x)}=\frac{\sum_{T\in t(p)}\prod_{t\in t\left(p\right),t\neq T}(x-t)}{\prod_{t\in t\left(p\right)}(x-t)}=\sum_{t\in t(p)}\frac{1}{x-t}$

考虑普通幂级数展开式，根据广义二项式定理有

$\frac{1}{x-t}=\sum_{r=0}^{+\infty}\binom{-1}{r}(-t)^{-1-r}x^{r}$

其 $x^{k}$ 项系数为

$\binom{-1}{k}(-t)^{-1-k}=\binom{-1}{k}(-1)^{k+1}\frac{1}{t^{k+1}}=-t^{k+1}$

因此和式 $\sum_{t\in t(p)}\frac{1}{x-t}$ 的 $x^{k+1}$ 项系数为

$\sum_{t\in t(p)} -t^{k+1}=-S_{k+1}$

因此

$\frac{f^{\prime}(x)}{f(x)}=\sum_{t\in t(p)}\frac{1}{x-t}=-(S_{1}+S_{2}x+S_{3}x^{2}+\cdots)$

$\frac{f(x) f^{\prime}(-x)+f(-x) f^{\prime}(x)}{f(x) f(-x)}=\frac{f^{\prime}(x)}{f(x)}+\frac{f^{\prime}(-x)}{f(-x)}=-2(S_{1}+x^{2} S_{3}+\cdots)$

另一方面，我们发现 $f(x)$ 有对称轴 $x=\frac{p}{2}$，因此

$f(x)=f(p-x)$

结合泰勒展开式，在 $(\bmod p^{2})$ 下有

$f(-x)=f(p+x) \equiv f(x)+p f^{\prime}(x)$

$f^{\prime}(-x)=-f^{\prime}(p+x) \equiv-f^{\prime}(x)-p f^{\prime \prime}(x)$

因此结合 $f(x)=x^{p-1}-1$ 有

$\begin{aligned}f(x) f^{\prime}(-x)+f^{\prime}(x) f(-x) &\equiv p\left\{f^{\prime 2}(x)-f(x) f^{\prime \prime}(x)\right\} \\&\equiv p\left(2 x^{p-3}-x^{2 p-4}\right)\left(\bmod p^{2}\right)\end{aligned}$

设 $\varpi=(p-1) !$，考虑展开过程，$f(x)$ 有如下形式

$f(x)=\prod(x-t)=\varpi\left(1+\frac{a_{1} x}{\varpi}+\frac{a_{2} x^{2}}{\varpi^{2}}+\cdots\right)$

$\frac{1}{f(x)}=\frac{1}{\varpi}\left(1+\frac{b_{1} x}{\varpi}+\frac{b_{2} x^{2}}{\varpi^{2}}+\cdots\right)$

$\frac{1}{f(x) f(-x)}=\frac{1}{\varpi^{2}}\left(1+\frac{c_{1} x^{2}}{\varpi^{2}}+\frac{c_{2} x^{4}}{\varpi^{4}}+\cdots\right)$

其中，数列 $\{a\},\{b\},\{c\}$ 都是整数，结合上面推导的式子有

$\begin{aligned}-2 (S_{1}+ x^{2} S_{3}+\cdots)= \frac{p\left(2 x^{p-3}-x^{2 p-4}\right)+p^{2} g(x)}{\varpi^{2}} \left(1+\frac{c_{1} x^{2}}{\varpi^{2}}+\frac{c_{2} x^{4}}{\varpi^{4}}+\cdots\right) \end{aligned}$

其中 $g(x)$ 是一个整系数多项式，考虑 $x^{2\nu}$ 项系数，当 $2\nu<p-3$ 时，有

$S_{2\nu+1}\equiv 0(\bmod p^{2})$

Theorem 131
若 $p$ 是素数，且 $2\nu<p-3$，设
$S_{2 \nu+1}=1+\frac{1}{2^{2 \nu+1}}+\cdots+\frac{1}{(p-1)^{2 \nu+1}}$
那么 $S_{2\nu+1}$ 的分子能被 $p^{2}$ 整除

$\nu=1$ 的情况就是 Wolstenholme's theorem

---

8、The residues of $2^{p-1}$ and $(p-1)!$ to modulus $p^{2}$

费马定理和威尔逊定理表明 $2^{p-1}$ 和 $(p-1)!$ 的剩余分别为 $1$ 和 $-1(\bmod p)$

接下来我们研究它们在 $(\bmod p^{2})$ 下的剩余

Theorem 132
若 $p$ 是奇素数，则
$\frac{2^{p-1}-1}{p} \equiv 1+\frac{1}{3}+\frac{1}{5}+\cdots+\frac{1}{p-2}(\bmod p)$

这个定理事实上就是

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

我们知道

$2^{p}=(1+1)^{p}=1+\binom{p}{1}+\cdots+\binom{p}{p}=2+\sum_{l=1}^{p-1}\binom{p}{l}$

根据 Theorem 75，设

$\binom{p}{l}=p x_{l}$

其中

$l ! x_{l}=(p-1)(p-2) \cdots(p-l+1) \equiv(-1)^{l-1}(l-1) !(\bmod p)$

$x_{l} \equiv(-1)^{l-1}\frac{1}{l}(\bmod p)$

因此

$\frac{2^{p}-2}{p}=\sum_{l=1}^{p-1} x_{l} \equiv 1-\frac{1}{2}+\frac{1}{3}-\cdots-\frac{1}{p-1}(\bmod p)$

根据 Theorem 116，

$\begin{aligned} 1-\frac{1}{2}+\frac{1}{3}-\cdots-\frac{1}{p-1}=& 2\left(1+\frac{1}{3}+\frac{1}{5}+\cdots+\frac{1}{p-2}\right) -\left(1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1}\right) \\ \equiv & 2\left(1+\frac{1}{3}+\cdots+\frac{1}{p-2}\right)(\bmod p) \end{aligned}$

证明完毕

Theorem 133
若 $p$ 是奇素数，则
$(p-1) ! \equiv(-1)^{\frac{1}{2}(p-1)} 2^{2 p-2}\left(\frac{p-1}{2} !\right)^{2}\left(\bmod p^{2}\right)$

设 $p=2n+1$，根据 Theorem 116 和 Theorem 132，

$\begin{aligned} \frac{(2 n) !}{2^{n} n !} &=1\times 3\times \cdots\times(2 n-1)=(p-2)(p-4) \cdots(p-2 n) \\(-1)^{n} \frac{(2 n) !}{2^{n} n !} & \equiv 2^{n} n !-2^{n} n ! p\left(\frac{1}{2}+\frac{1}{4}+\cdots+\frac{1}{2 n}\right)\left(\bmod p^{2}\right) \\ & \equiv 2^{n} n !+2^{n} n !\left(2^{2 n}-1\right)\left(\bmod p^{2}\right) \end{aligned}$

因此

$(2 n) ! \equiv(-1)^{n} 2^{4 n}(n !)^{2}\left(\bmod p^{2}\right)$

证明完毕

---

附：浙江大学数论导引期末考试题

（1）证明卢卡斯同余式：对任意素数 $p$，均有

$\binom{p-1}{x} \equiv(-1)^{x}(\bmod p), \quad 0 \leq x \leq p-1$

进一步证明，当 $p>1$ 不为素数时，上式不总是成立

（2）设 $p$ 是奇素数，证明

$\frac{2^{p}-2}{p} \equiv 1-\frac{1}{2}+\frac{1}{3}-\ldots-\frac{1}{p-1}(\bmod p)$

注：有理数的同余式 $\frac{a}{b} \equiv \frac{c}{d}(\bmod m)$ 意味着 $(b d, m)=1, m | (a d-b c)$