拉格朗日定理：设ppp为素数，对于模ppp意义下的整数系多项式
f(x)=anxn+an−1xn−1+⋯+a0(p∤an)f\left(x\right) = a_n x^n + a_{n - 1} x^{n - 1} + \cdots + a_0 \left( p \nmid a_n\right) f(x)=an​xn+an−1​xn−1+⋯+a0​(p∤an​)
的同余方程f(x)≡0(modp)f\left(x\right)\equiv 0 \left(\mathop{mod} p\right)f(x)≡0(modp)在模ppp意义下至少有nnn个不同的解
（xi≢xj(modp),∀i≠jx_i \not\equiv x_j \left(\mathop{mod} p \right),\quad \forall i\neq jxi​≡xj​(modp),∀i=j）

证明：
n=0n = 0n=0时显然成立
假设degf 利用反证法：假设存在一个满足题目条件的fff在模ppp意义下有着至少n+1n+1n+1个不同的解x0,x1,⋯,xnx_0,x_1,\cdots, x_nx0​,x1​,⋯,xn​
设f(x)−f(x0)=(x−x0)g(x)f\left(x\right) - f\left(x_0\right) = \left(x - x_0\right) g\left(x\right)f(x)−f(x0​)=(x−x0​)g(x)
则g(x)g\left(x\right)g(x)在模ppp意义下时一个至多n−1n-1n−1次多项式

对于1≤i≤n1\le i \le n1≤i≤n,有
(xi−x0)g(xi)≡f(xi)−f(x0)≡0(modp)\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(\mathop{mod} p\right) (xi​−x0​)g(xi​)≡f(xi​)−f(x0​)≡0(modp)
又因为xi≢xj(modp),∀i≠jx_i \not\equiv x_j \left(\mathop{mod} p \right),\quad \forall i\neq jxi​≡xj​(modp),∀i=j
故g(xi)≡0(modp)g\left(x_i\right)\equiv 0\left(\mathop{mod} p\right)g(xi​)≡0(modp),从而g(x)≡0(modp)g\left(x\right) \equiv 0 \left(\mathop{mod} p\right)g(x)≡0(modp)至少有nnn个根，矛盾