Congruence equation

对正整数 \(m\) 和一元整系数多项式 \(f(x)=\sum_{i=0}^n a_ix^i\)，其中未知数 \(x\in\mathbf{Z}_m\)，称形如

的方程为关于未知数 \(x\) 的模 \(m\) 的一元 同余方程（Congruence Equation）。

若 \(a_n\not\equiv 0\pmod m\)，则称上式为 \(n\) 次同余方程。

类似可定义同余方程组。

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

整理后可得

于是

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

对 \(k\) 应用数学归纳法。

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

  由 \(f(x_1)\equiv 0\pmod p\) 可知 \(r\equiv 0\pmod p\)，从而 \(f(x)\equiv(x-x_1)g(x)\pmod p\).

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

  \[ (\forall i=2,3,\dots,k),~~0\equiv f(x_i)\equiv (x_i-x_1)h(x_i)\pmod p \]

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

  \[ h(x)\equiv g(x)\prod_{i=2}^k(x-x_i)\pmod p \]

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

  因此命题得证。

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

令 \(x=x_{n+1}\), 则

而右侧显然不是 \(p\) 的倍数，因此假设矛盾。

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

其中 \(\deg r<p\).

由 Fermat 小定理 知对任意整数 \(x\) 有 \(x^p\equiv x\pmod p\)，从而

• 若 \(r(x)\equiv 0\pmod p\)，则由 推论 2 可知 \(f(x)\) 有 \(p\) 个不同的解。
• 若 \(r(x)\not\equiv 0\pmod p\)，则由 \(f(x)\equiv r(x)\pmod p\) 可知 \(f(x)\) 和 \(r(x)\) 的解集相同。

• 必要性：由多项式除法知存在整系数多项式 \(q(x)\)，\(r_1(x)~(\deg r_1 < n)\) 使得

  \[ x^p-x=f(x)q(x)+r_1(x) \]

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

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

  \[ 0\equiv x^p-x\equiv f(x)q(x)\pmod p \]

  即方程 \(f(x)q(x)\equiv 0\pmod p\) 有 \(p\) 个解。

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

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

  因此 \(s=n\).

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

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

  \[ a^{\frac{p-1}{n}}\equiv {\left(x_0^n\right)}^{\frac{p-1}{n}}\equiv 1\pmod p \]

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

  \[ \begin{aligned} x^p-x&=x\left(x^{p-1}-1\right)\\ &=x\left(\left(x^n\right)^{\frac{p-1}{n}}-a^{\frac{p-1}{n}}+a^{\frac{p-1}{n}}-1\right)\\ &=\left(x^n-a\right)P(x)+x\left(a^{\frac{p-1}{n}}-1\right)\\ \end{aligned} \]

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