拉格朗日定理

定义

拉格朗日定理：设为素数，对于模意义下的整系数多项式

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\nmid a_0$ ，故 $f(x)\equiv 0\pmod p$ 无解，定理对的多项式都成立。

若命题对于 $\deg f<n$ 的都成立，由反证法，假设存在一个满足题目条件的在模意义下有着至少个不同的解 $x_0,x_1,\cdots,x_{n}$ 。

可设，则在模意义下是一个至多次的多项式。现在由 $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$ 有至少个根，与归纳假设矛盾。

所以，命题对次多项式也成立，定理获证。

证毕

应用

首先见群论部分的群论基础有关群和元素的阶的定义，以及相关定理。

给出一个关于同余方程的引理：

对于任意，至多有个不同的满足同余方程 $nx\equiv a\pmod m$ 。

证明

反证法。如果存在不同的解 $x_1 x_2\ldots x_{n+1}$ 都满足该方程，那么对于方程 $n(x-x_{n+1})\equiv 0\pmod m$ 也至少有这个解。

设 m 与 n 的最大公约数为 d，，那么上述方程可以简化为 $d(x-x_{n+1})\equiv 0\pmod {m_0d}$ 。所有的解在模意义下都与同余，根据中国剩余定理，在模意义下的至多有个，而是的约数，不可能大于，这与假设矛盾，因此原命题成立。

拉格朗日定理可以用在一个抽象代数中的定理中：

在有限可交换群中，以下两个条件等价：
是循环群。
对于任意一个元素，至多有个不同的元素满足条件。

证明

先证循环群推个元素条件。如果是循环群，那么每个元素都可以表示成为生成元的幂的形式。

于是将不同的元素记为，记为，条件变为 $g^{yn}=g^z$ 。如果群的阶为，则条件等价于 $yn\equiv z\pmod m$ 。于是这部分根据引理得证。

再证个元素条件推循环群。如果中对于任意元素，至多个使得。取为单位元，即。

根据元素的阶部分的定理，群中必然存在元素，阶是所有元素的倍数。对于这个阶，所有的元素都满足。那么，根据初始条件，这个至少为群的阶。

但是显然不能比大，否则会产生重复现象，即存在不同的整数和使得。因此只能有，元素的幂次恰好把群的所有元素不重不漏地跑了一遍，所以是循环群，是生成元。证完。

因此可以直接得到结论：

对于素数，模的缩剩余系 $Z_p^\ast$ 对于乘法构成的群是循环群。

另外阅读后文原根也可以知道，如果模的原根存在，那么自然也会满足上述性质「对于任意一个元素，至多有个不同的元素满足条件 $x^n\equiv a\pmod m$ 」。

本页面最近更新：2023/3/22 15:46:23，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：iamtwz, aofall, CCXXXI, CoelacanthusHex, Great-designer, Marcythm, Persdre, shuzhouliu, Tiphereth-A, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用