拉格朗日定理

拉格朗日定理（数论）

设 $p$ 为素数，对于模 $p$ 意义下的整系数多项式

$$f(x) = a_n x^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 \not\mid a_0$ ，

故 $f(x) \equiv 0 \pmod{p}$ 无解，定理对 $n=0$ 的多项式 $f(x)$ 都成立。

若命题对于 $\operatorname{deg} f < n$ 的 $f$ 都成立（这里 $\operatorname{deg}$ 表示多项式的次数）

由反证法，假设存在一个满足题目条件的 $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}$ 的解，可知对 $i=1,2,\cdots,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 \pmod{p}$$

而 $x_i \not\equiv x_0 \pmod{p}$ ，故 $g(x_i) \equiv 0 \pmod{p}$ ，从而 $g(x_i) \equiv 0 \pmod{p}$ 有至少 $n$ 个根，与假设矛盾。

因此命题对于 $n$ 次多项式也成立。证毕。

---

拉格朗日定理（群论）

定理：设 $H$ 是有限群 $G$ 的子群，则 $H$ 的阶整除 $G$​ 的阶。

由拉格朗日定理可立即得到：群中任意一个元素的阶，一定整除群的阶。

关于这部分，可以来看 群论基础 这篇文章。

---

参考文献：

[1] https://www.luogu.com.cn/blog/codecodeakioi/solution-p6091