定义
拉格朗日定理：设 \(p\) 为素数，对于模 \(p\) 意义下的整系数多项式
\[f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0(p\not\mid a_n)
\]
的同余方程 \(f(x)\equiv 0\pmod p\) 在模 \(p\) 意义下至多有 \(n\) 个不同解。
证明
对 \(n\) 使用归纳法。当 \(n=0\) 时，由于 \(p\nmid a_0\)，故 \(f(x)\equiv 0\pmod p\) 无解，定理对 \(n=0\) 的多项式 \(f(x)\) 都成立。
若命题对于 \(\deg f<n\) 的 \(f\) 都成立，由反证法，假设存在一个满足题目条件的 \(f\) 在模 \(p\) 意义下有着至少 \(n+1\) 个不同的解 \(x_0,x_1,\cdots,x_{n}\)。
可设 \(f(x)-f(x_0)=(x-x_0)g(x)\)，则 \(g(x)\) 在模 \(p\) 意义下是一个至多 \(n-1\) 次的多项式。现在由 \(x_0,x_1,\cdots,x_n\) 都是 \(f(x)\equiv 0\pmod p\) 的解，知对 \(1\leq i\leq n\)，都有
\[(x_i-x_0)g(x_i)\equiv f(x_i)-f(x_0)\equiv 0\pmod p
\]
而 \(x_i \not\equiv x_0 \pmod p\)，故 \(g(x_i)\equiv 0\pmod p\)，从而 \(g(x)\equiv 0\pmod p\) 有至少 \(n\) 个根，与归纳假设矛盾。
所以，命题对 \(n\) 次多项式也成立，定理获证。
证毕