同余方程

对素数 $p$ 和整数 ，取整系数多项式 $f(x)=\sum _{i=0}^n{a}_i{x}^i(p^e\nmid a_n)$，令 $f^{\prime }(x)=\sum _{i=1}^{n}i{a}_i{x}^{i-1}$ 为其导数．令 $x_0$ 为方程

$$\begin{array}{}\text{(2)}& f(x)\equiv 0(\mathrm{mod}{p}^{e-1})\end{array}$$

的解，则：

1. 若 $f^{\prime }(x_0)\not\equiv 0(\mathrm{mod}p)$，则存在整数 $t$ 使得

   $$\begin{array}{}\text{(3)}& x=x_0+p^{e-1}t\end{array}$$

   是方程

   $$\begin{array}{}\text{(4)}& f(x)\equiv 0(\mathrm{mod}{p}^e)\end{array}$$

   的解．

2. 若 $f^{\prime }(x_0)\equiv 0(\mathrm{mod}p)$ 且 $f(x_0)\equiv 0(\mathrm{mod}{p}^e)$，则对 $t=0,1,\dots ,p-1$，由式 $(3)$ 确定的 $x$ 均为方程 $(4)$ 的解．

3. 若 $f^{\prime }(x_0)\equiv 0(\mathrm{mod}p)$ 且 $f(x_0)\not\equiv 0(\mathrm{mod}{p}^e)$，则不能由式 $(3)$ 构造方程 $(4)$ 的解．

我们假设式 $(3)$ 是方程 $(4)$ 的解，即

$$f(x_0+p^{e-1}t)\equiv 0(\mathrm{mod}{p}^e)$$

整理后可得

$$f(x_0)+p^{e-1}t{f}^{\prime }(x_0)\equiv 0(\mathrm{mod}{p}^e)$$

于是

$$\begin{array}{}\text{(5)}& t{f}^{\prime }(x_0)\equiv -\frac{f(x_0)}{p^{e-1}}(\mathrm{mod}p)\end{array}$$

1. 若 $f^{\prime }(x_0)\not\equiv 0(\mathrm{mod}p)$，则关于 $t$ 的方程 $(5)$ 有唯一解 $t_0$，代入式 $(3)$ 可验证其为方程 $(4)$ 的解．
2. 若 $f^{\prime }(x_0)\equiv 0(\mathrm{mod}p)$ 且 $f(x_0)\equiv 0(\mathrm{mod}{p}^e)$，则任意 $t$ 均能使方程 $(5)$ 成立，代入式 $(3)$ 可验证其均为方程 $(4)$ 的解．
3. 若 $f^{\prime }(x_0)\equiv 0(\mathrm{mod}p)$ 且 $f(x_0)\not\equiv 0(\mathrm{mod}{p}^e)$，则方程 $(5)$ 无解，从而不能由式 $(3)$ 构造方程 $(4)$ 的解．

对 定理 1 的 $p$，$e$，$f(x)$，$x_0$，

1. 若 $s$ 是方程 $f(x)\equiv 0(\mathrm{mod}p)$ 的解，且 $f^{\prime }(s)\not\equiv 0(\mathrm{mod}p)$，则存在 $x_s\in {\mathbf{Z}}_{p^e}$，$x_s\equiv s(\mathrm{mod}p)$ 使得 $x_s$ 是方程 $(4)$ 的解．
2. 若方程 $f(x)\equiv 0(\mathrm{mod}p)$ 与 $f^{\prime }(x)\equiv 0(\mathrm{mod}p)$ 无公共解，则方程 $(4)$ 和方程 $f(x)\equiv 0(\mathrm{mod}p)$ 的解数相同．

若方程

$$\begin{array}{}\text{(6)}& f(x)\equiv 0(\mathrm{mod}p)\end{array}$$

有 $k$ 个不同的解 $x_1,x_2,\dots ,x_k(k\le n)$，则

$$f(x)\equiv g(x)\prod _{i=1}^k(x-x_i)(\mathrm{mod}p),$$

其中 $\mathrm{deg}g=n-k$ 且 $[x^{n-k}]g(x)=a_n$．

对 $k$ 应用数学归纳法．

• 当 $k=1$ 时，做多项式带余除法，有 $f(x)=(x-x_1)g(x)+r$，其中 $r\in \mathbf{Z}$．

  由 $f(x_1)\equiv 0(\mathrm{mod}p)$ 可知 $r\equiv 0(\mathrm{mod}p)$，从而 $f(x)\equiv (x-x_1)g(x)(\mathrm{mod}p)$．

• 假设命题对 $k-1$() 时的情况成立，现在设 $f(x)$ 有 $k$ 个不同的解 $x_1,x_2,\dots ,x_k$，则 $f(x)\equiv (x-x_1)h(x)(\mathrm{mod}p)$，进而有

  $$(\mathrm{\forall }i=2,3,\dots ,k),0\equiv f(x_i)\equiv (x_i-x_1)h(x_i)(\mathrm{mod}p)$$

  从而 $h(x)$ 有 $k-1$ 个不同的解 $x_2,x_3,\dots ,x_k$，由归纳假设有

  $$h(x)\equiv g(x)\prod _{i=2}^k(x-x_i)(\mathrm{mod}p)$$

  其中 $\mathrm{deg}g=n-k$ 且 $[x^{n-k}]g(x)=a_n$．

  因此命题得证．

对素数 $p$，

• $(\mathrm{\forall }x\in \mathbf{Z}),x^{p-1}-1\equiv \prod _{i=1}^{p-1}(x-i)(\mathrm{mod}p)$．
• （Wilson 定理）$(p-1)!\equiv -1(\mathrm{mod}p)$．

方程 $(6)$ 至多有 $n$ 个不同解．

假设 $f(x)$ 有 $n+1$ 个不同解 $x_1,x_2,\dots ,x_{n+1}$，则由 定理 2，对 $x_1,x_2,\dots ,x_n$ 有

$$f(x)\equiv a_n\prod _{i=1}^n(x-x_i)(\mathrm{mod}p)$$

令 $x=x_{n+1}$，则

$$0\equiv f(x_{n+1})\equiv a_n\prod _{i=1}^n(x_{n+1}-x_i)(\mathrm{mod}p)$$

而右侧显然不是 $p$ 的倍数，因此假设矛盾．

若同余方程 $\sum _{i=0}^n{b}_i{x}^i\equiv 0(\mathrm{mod}p)$ 的解数大于 $n$，则

$$(\mathrm{\forall }i=0,1,\dots ,n),p\mid b_i.$$

方程 $(6)$ 若解的个数不为 $p$，则必存在满足 的整系数多项式 $r(x)$ 使得 $f(x)\equiv 0(\mathrm{mod}p)$ 和 $r(x)\equiv 0(\mathrm{mod}p)$ 的解集相同．

不妨设 $n\ge p$，对 $f(x)$ 做多项式带余除法

$$f(x)=g(x)(x^p-x)+r(x)$$

其中 ．

由 Fermat 小定理 知对任意整数 $x$ 有 $x^p\equiv x(\mathrm{mod}p)$，从而

• 若 $r(x)\equiv 0(\mathrm{mod}p)$，则由 推论 2 可知 $f(x)$ 有 $p$ 个不同的解．
• 若 $r(x)\not\equiv 0(\mathrm{mod}p)$，则由 $f(x)\equiv r(x)(\mathrm{mod}p)$ 可知 $f(x)$ 和 $r(x)$ 的解集相同．

设 $n\le p$，则方程

$$\begin{array}{}\text{(7)}& x^n+\sum _{i=0}^{n-1}{a}_i{x}^i\equiv 0(\mathrm{mod}p)\end{array}$$

有 $n$ 个解当且仅当存在整系数多项式 $q(x)$， 使得

$$\begin{array}{}\text{(8)}& x^p-x=f(x)q(x)+pr(x).\end{array}$$

• 必要性：由多项式除法知存在整系数多项式 $q(x)$， 使得

  $$x^p-x=f(x)q(x)+r_1(x).$$

  若方程 $(7)$ 有 $n$ 个解，则 $r_1\equiv 0(\mathrm{mod}p)$ 也有 $n$ 个相同的解，进而由 推论 3 可知存在整系数多项式 $r(x)$ 满足 $r_1(x)=pr(x)$，从而命题得证．

• 充分性：若式 $(8)$ 成立，则由 Fermat 小定理 可知，对任意整数 $x$,

  $$0\equiv x^p-x\equiv f(x)q(x)(\mathrm{mod}p).$$

  即方程 $f(x)q(x)\equiv 0(\mathrm{mod}p)$ 有 $p$ 个解．

  设方程 $(7)$ 的解数为 $s$，则由 Lagrange 定理 可知 $s\le n$．

  又由于 $\mathrm{deg}q=p-n$，则由 Lagrange 定理 可知 $q(x)\equiv 0(\mathrm{mod}p)$ 的解数不超过 $p-n$，而方程 $f(x)q(x)\equiv 0(\mathrm{mod}p)$ 的解集是 $f(x)\equiv 0(\mathrm{mod}p)$ 解集和 $q(x)\equiv 0(\mathrm{mod}p)$ 解集的并集，故 $s+(p-n)\ge p$，有 $s\ge n$．

  因此 $s=n$．

设 $n\nmid p-1$，$p\nmid a$，则方程

$$\begin{array}{}\text{(9)}& x^n\equiv a(\mathrm{mod}p)\end{array}$$

有解当且仅当

$$a^{\frac{p-1}{n}}\equiv 1(\mathrm{mod}p).$$

而且，若 $(9)$ 有解，则解数为 $n$．

方程 $(9)$ 解集的具体结构可参见 k 次剩余．

• 必要性：若方程 $(9)$ 有解 $x_0$，则

  $$a^{\frac{p-1}{n}}\equiv {\left(x_0^n\right)}^{\frac{p-1}{n}}\equiv 1(\mathrm{mod}p)$$

• 充分性：若 $a^{\frac{p-1}{n}}\equiv 1(\mathrm{mod}p)$，则

  

  其中 $P(x)$ 是某个整系数多项式，因此由 定理 5 可知方程 $(9)$ 有 $n$ 个解．