拉格朗日定理

拉格朗日定理：设$p$为素数，对于模$p$意义下的整数系多项式
$$f\left(x\right)=a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots +a_0\left(p\nmid a_n\right)$$
的同余方程$f\left(x\right)\equiv 0\left(\mathrm{mod}p\right)$在模$p$意义下至少有$n$个不同的解
（$x_i\not\equiv x_j\left(\mathrm{mod}p\right),\forall i\ne j$）

证明：
$n=0$时显然成立
假设$\mathrm{deg}f<n$时都成立
利用反证法：假设存在一个满足题目条件的$f$在模$p$意义下有着至少$n+1$个不同的解$x_0,x_1,\cdots ,x_n$
设$f\left(x\right)-f\left(x_0\right)=\left(x-x_0\right)g\left(x\right)$
则$g\left(x\right)$在模$p$意义下时一个至多$n-1$次多项式

对于$1\le i\le n$,有
$$\left(x_i-x_0\right)g\left(x_i\right)\equiv f\left(x_i\right)-f\left(x_0\right)\equiv 0\left(\mathrm{mod}p\right)$$
又因为$x_i\not\equiv x_j\left(\mathrm{mod}p\right),\forall i\ne j$
故$g\left(x_i\right)\equiv 0\left(\mathrm{mod}p\right)$,从而$g\left(x\right)\equiv 0\left(\mathrm{mod}p\right)$至少有$n$个根，矛盾