拉格朗日定理
定义
拉格朗日定理：设 \(p\) 为素数，对于模 \(p\) 意义下的整系数多项式
的同余方程 \(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 \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\) 在模 \(m*0\) 意义下都与 \(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\)」。
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用