素数模同余式

$$f(x)\equiv 0(modp)$$

---

素数模 p 的同余式与一个次数不超过 $p-1$ 的素数模同余式等价

由 多项式的带余除法 或者用 费马定理 降次

$$f(x)=(x^p-x)q(x)+r(x),deg(r(x))\le p-1$$

由 费马定理 得 $x^p-x\equiv 0(modp)$，所以 $f(x)$ 和 $r(x)$ 等价

---

如

$$x\equiv \beta (modp)$$

是素数同余式的其中一个解，则有

$$f(x)\equiv (x-\beta )f_{n-1}(x)(modp)$$

递归展开，如有不同的解 ${\beta }_1,{\beta }_2,\dots ,{\beta }_k$，根据上式代入 ${\beta }_2$ 展开递归下去得：

$$f(x)\equiv (x-{\beta }_1)(x-{\beta }_2)\dots (x-{\beta }_k)f_{n-k}(x)(modp)$$ $$deg(f_{n-k}(x))=n-k$$

---

由 费马定理 得：

$$x^{p-1}\equiv 1(modp)$$

证明 1 到 p-1 都是上面的解

$$x^{p-1}-1\equiv (x-1)(x-2)\dots (x-(p-1))(modp)$$

将 $x\equiv 0$ 代入

$$(p-1)!+1\equiv 0(modp)$$

威尔逊定理

---

素数模同余式解的个数不超过它的次数

反证法，前 n 个作为因子，剩余的函数是一个整数，如果代入 0 的话左右不相等

如有 $n\le p$ 个解，那么 首一多项式 $f(x)$ 满足

$$f(x)|x^p-x$$

即最大解的个数了

解素数同余式