模p多项式根定理

作者: 摇摆苏丹 | 来源:发表于2021-01-25 14:21 被阅读0次

模p多项式根定理
高等代数理论基础9：复系数与实系数多项式
高等代数理论基础53：最小多项式
高等代数理论基础6：因式分解定理
近世代数理论基础7：同余式·中国剩余定理
33.整函数的中值定理
第 0章：Matlab简介
同余
高等代数理论基础77：A-矩阵应用
基于sklearn的朴素贝叶斯分类器

引言

对于多项式方程，根据代数基本定理，我们能算出其根的数量。对于同余式，是否也有相似的定理？没错，它就是模p多项式根定理。

表述

设 $p$ 为素数， $f(x) = a_0x^d + a_1x^{d-1} + \cdots + a_d$ 是次数为 $d \geq 0$ 的整系数多项式，且 $p \nmid a_0$ ，则同余式 $f(x) \equiv 0 \ (mod \ p)$ 最多有 $d$ 个模 $p$ 不同余的解（可简写为最多有 $d$ 个解）。

证明

原命题的反命题是：至少存在一个首项系数不被 $p$ 整除的整系数多项式 $F(x)$ ，使得同余式 $F(x) \equiv 0 \ (mod \ p)$ 根的个数大于 $F(x)$ 的次数。现在用反证法证明这个反命题不成立。
在所有满足上述条件中的多项式中取一个次数最低的，设为：
$F(x) = A_0x^d + A_1x^{d-1} + \cdots + A_d$
注意，满足上述条件的多项式中一定存在一个次数最低的。容易证明，当 $d=0$ 时， $F(x)=A_d$ ，又 $p \nmid A_d$ ，则 $F(x) \equiv 0 \ (mod \ p)$ 无解，此时原命题成立，原命题的反命题不成立。我们关心的是，当 $d \geq 1$ 的时候，是否存在 $d$ 使得 $F(x) \equiv 0 \ (mod \ p)$ 有 $d+1$ 甚至更多个解。可以假设这样的 $d$ 存在，但是 $d$ 一定有最小值。
设 $F(x)$ 的一组解为：
$r_1,r_2,\cdots,r_{d+1}$
取其中一个特解 $r_1$ ，令其为 $r$ ，则有 $F(r) \equiv 0 \ (mod \ p)$ ，以及 $F(x)-F(r) \equiv 0 \ (mod \ p)$ 。
$\begin{array}{c} F(x)-F(r)= A_0x^d + A_1x^{d-1} + \cdots + A_d - (A_0r^d + A_1r^{d-1} + \cdots + A_d) \\ F(x)-F(r)= A_0(x^d-r^d) + A_1(x^{d-1}-r^{d-1}) + \cdots + A_{d-1}(x-r) \end{array}$
对于 $x^i-r^i$ ，总能提出因式 $x-r$ ，因此：
$F(x)-F(r)= (x-r)G(x) \equiv 0 \ (mod \ p)$
其中 $G(x)$ 是另一个多项式，其最高次数为 $d-1$ 。令 $r$ 为特解 $r_1$ ，令 $r_k$ 为 $r_1$ 模 $p$ 不同余的另一个解，得到：
$F(r_k)-F(r_i) = (r_k-r_i)G(r_k) \equiv 0 \ (mod \ p)$
由于 $r_k$ 与 $r_1$ 模 $p$ 不同余， $p$ 为质数，所以 $p \mid G(r_k)$ ，即 $G(r_k) \equiv 0 \ (mod \ p)$ 。 $r_k$ 可以取除了 $r_1$ 的所有 $d$ 个根，对于 $G(x)$ 来说， $r_2,r_2,\cdots,r_{d+1}$ 都是它的根。于是 $G(x)$ 就成了次数为 $d-1$ ，但是有 $d$ 个模 $p$ 不同余的根的多项式， $G(x)$ 的根的个数大于其次数，但是 $G(x)$ 的次数小于 $F(x)$ ，于是 $F(x)$ 不是次数最低的那个多项式，原命题的反命题存在矛盾，因此原命题得证。