素数模同余式

1. 基本形式

设 $p$ 是素数，$f(x)$ 是整系数多项式： $f(x)=a_n{x}^n+\cdots +a_{1}x+a_0\equiv 0(\mathrm{mod}p)$ 且首项系数 $a_n$ 不能被 $p$ 整除。

2. 降次原则 (核心解题技巧)

由于模数为素数 $p$，根据 3.1 费马小定理，对于任意整数 $x$，都有 $x^p\equiv x(\mathrm{mod}p)$。 由此可得以下多项式等价关系： $x^p-x\equiv 0(\mathrm{mod}p)$

应用方法： 利用多项式除法，将 $f(x)$ 除以 $(x^p-x)$： $f(x)=(x^p-x)q(x)+r(x)$ 其中余式 $r(x)$ 的次数必定小于 $p$。 结论：解高次同余式 $f(x)\equiv 0(\mathrm{mod}p)$ 等价于解降次后的同余式 $r(x)\equiv 0(\mathrm{mod}p)$。

3. 核心定理

拉格朗日定理 (同余式版)

在模 $p$ 为素数的情况下，次数为 $n$ 的同余式 $f(x)\equiv 0(\mathrm{mod}p)$ 至多有 $n$ 个解。 注意：如果模数是合数，此结论不成立（例如 $x^2\equiv 1(\mathrm{mod}8)$ 有 4 个解）。

威尔逊定理

$p$ 是素数的充分必要条件是： $(p-1)!\equiv -1(\mathrm{mod}p)$ 或者写作 $(p-1)!+1\equiv 0(\mathrm{mod}p)$。 这是判定素数的一个重要理论依据。

4. 解题示例

题目：解模 3 的同余式 $5x^{15}+x^{14}+x^{10}+8x^5+7x^2+x+11\equiv 0(\mathrm{mod}3)$

解：

1. 系数化简：先将所有系数模 3 化简。 $2x^{15}+x^{14}+x^{10}+2x^5+x^2+x+2\equiv 0(\mathrm{mod}3)$
2. 降次：利用 $x^3\equiv x(\mathrm{mod}3)$ (即 $x^3-x\equiv 0$)。 对多项式进行带余除法（或反复利用 $x^k\equiv x^{k-2}$ 替换，因为 $x^3=x⟹x^4=x^2\dots$）：
   • $x^{15}\equiv x$
   • $x^{14}\equiv x^2$
   • $x^{10}\equiv x^2$
   • $x^5\equiv x$
3. 代入整理： $2(x)+(x^2)+(x^2)+2(x)+x^2+x+2\equiv 0(\mathrm{mod}3)$ $3x^2+5x+2\equiv 0(\mathrm{mod}3)$
4. 再次模 3 化简： $0x^2+2x+2\equiv 0(\mathrm{mod}3)$ $2x\equiv -2\equiv 1(\mathrm{mod}3)$
5. 求解： $2x\equiv 1⟹2x\equiv 4(\mathrm{mod}3)⟹x\equiv 2(\mathrm{mod}3)$。