素数模 p 的同余式与一个次数不超过 的素数模同余式等价
由 费马定理 得 ，所以 和 等价
如
是素数同余式的其中一个解，则有
递归展开，如有不同的解 ，根据上式代入 展开递归下去得：
由 费马定理 得：
证明 1 到 p-1 都是上面的解
将 代入
素数模同余式解的个数不超过它的次数
反证法，前 n 个作为因子，剩余的函数是一个整数，如果代入 0 的话左右不相等
如有 个解，那么 首一多项式 满足
即最大解的个数了
2024年10月28日2分钟阅读
素数模 p 的同余式与一个次数不超过 p−1 的素数模同余式等价
f(x)=(xp−x)q(x)+r(x),deg(r(x))≤p−1由 费马定理 得 xp−x≡0(modp)，所以 f(x) 和 r(x) 等价
如
x≡β(modp)是素数同余式的其中一个解，则有
f(x)≡(x−β)fn−1(x)(modp)递归展开，如有不同的解 β1,β2,…,βk，根据上式代入 β2 展开递归下去得：
f(x)≡(x−β1)(x−β2)…(x−βk)fn−k(x)(modp) deg(fn−k(x))=n−k由 费马定理 得：
xp−1≡1(modp)证明 1 到 p-1 都是上面的解
xp−1−1≡(x−1)(x−2)…(x−(p−1))(modp)将 x≡0 代入
(p−1)!+1≡0(modp)反证法，前 n 个作为因子，剩余的函数是一个整数，如果代入 0 的话左右不相等
如有 n≤p 个解，那么 首一多项式 f(x) 满足
f(x)∣xp−x即最大解的个数了