拉格朗日定理

拉格朗日定理:设 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<nf 都成立,由反证法,假设存在一个满足题目条件的 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^ya 记为 g^z,条件变为 g^{yn}=g^z。如果群的阶为 m,则条件等价于 yn\equiv z\pmod m。于是这部分根据引理得证。

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

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

但是显然 d 不能比 m 大,否则会产生重复现象,即存在不同的整数 ij 使得 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”。


评论