哈代数论读书笔记(八)——模合数意义下的同余

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 116Theorem 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)$

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

发表评论

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