拉格朗日定理

定义

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

的同余方程 在模 意义下至多有 个不同解。

证明

使用归纳法。当 时,由于 ,故 无解,定理对 的多项式 都成立。

若命题对于 都成立,由反证法,假设存在一个满足题目条件的 在模 意义下有着至少 个不同的解

可设 ,则 在模 意义下是一个至多 次的多项式。现在由 都是 的解,知对 ,都有

,故 ,从而 有至少 个根,与归纳假设矛盾。

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

证毕

应用

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

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

对于任意 ,至多有 个不同的 满足同余方程

证明

反证法。如果存在不同的解 都满足该方程,那么对于方程 也至少有这 个解。

设 m 与 n 的最大公约数为 d,,那么上述方程可以简化为 。所有的解 在模 意义下都与 同余,根据中国剩余定理,在模 意义下的 至多有 个,而 的约数,不可能大于 ,这与假设矛盾,因此原命题成立。

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

在有限可交换群 中,以下两个条件等价:

是循环群。

对于任意一个元素 ,至多有 个不同的元素 满足条件

证明

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

于是将不同的元素 记为 记为 ,条件变为 。如果群的阶为 ,则条件等价于 。于是这部分根据引理得证。

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

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

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

因此可以直接得到结论:

对于素数 ,模 的缩剩余系 对于乘法构成的群是循环群。

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


评论