拉格朗日定理

设 \(p\) 为素数，在模 \(p\) 意义下的 \(n\) 次多项式 \(f(x) = a_n\cdot x^n+\cdots+a_1\cdot x+a_0 (p\nmid a_n)\) ，那么同余方程 \(f(x)\equiv 0\pmod p\) 在模 \(p\) 意义下最多有 \(n\) 个不同的解。

证明

对 \(n\) 使用数学归纳法。

当 \(n=0\) 时，由于 \(p\not\mid a_0\) ，所以方程无解。那么当 \(n=0\) 是定理成立。

假设命题对次数小于 \(n\) 的多项式都成立。

通过证明如果 \(n\) 次多项式有 \(n+1\) 个解，那么 \(n-1\) 次多项式有 \(n\) 个解来推出矛盾。

• 考虑次数为 \(n\) 的多项式。如果存在一个 \(n\) 次多项式 \(f(x)\) ，使得 \(f(x)\equiv 0\pmod p\) 在模 \(p\) 意义下有 \(n+1\) 个不同解 \(x_0, x_1,\dots,x_n\) 。
  因式分解可得 \(f(x)=(x-x_0)\cdot g(x)\) ，其中 \(g(x)\) 在模 \(p\) 意义下是一个至多 \(n-1\) 次的多项式。所以对任意 \(x_i (1\leq i\leq n)\) ，有：
  \[(x_i-x_0)g(x_i)\equiv f(x_i)\equiv 0\pmod p\]
  而 \(x_i\not\equiv x_0\pmod p\) ，所以 \(g(x_i)\equiv 0\pmod p\) ，从而 \(g(x)=0\pmod p\) 在模 \(p\) 意义下至少有 \(n\) 个解，与归纳假设矛盾。

所以定理对 \(n\) 次多项式也成立。