拉格朗日定理

拉格朗日定理：设 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 次多项式也成立，定理获证。

证毕

应用

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

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

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

证明

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

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

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

在有限可交换群 G 中，以下两个条件等价：

G 是循环群。

对于任意一个元素 a ，至多有 n 个不同的元素 x 满足条件 x^n=a 。

证明

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

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

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

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

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

因此可以直接得到结论：

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

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

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论