☰本讲目录
◎学习目标
- 理解欧拉函数 \(\varphi(n)\) 的定义，会对小的 \(n\) 通过逐一枚举计算 \(\varphi(n)\)；
- 熟记欧拉定理的表述：\(\gcd(a,n)=1 \Rightarrow a^{\varphi(n)} \equiv 1 \pmod n\)，并能用小例子验证；
- 会用欧拉定理计算大指数幂模 \(n\) 的余数（如 \(7^{222} \bmod 10\)）；
- 掌握欧拉定理的群论证明总思路：构造 \(G = \{\) 小于 \(n\) 且与 \(n\) 互素的正整数 \(\}\)，\(|G| = \varphi(n)\)，并证明 \(G\) 是群；
- 会验证 \(G\) 上「模 \(n\) 乘法」运算的合理性与封闭性，会用 Bézout 恒等式构造逆元；
- 理解如何应用拉格朗日定理的推论（有限群中任一元素的群阶次幂等于单位元）完成证明，并把 \(a > n\) 的情形归结为余数的情形；
- 能从欧拉定理推出费马小定理 \(a^{p} \equiv a \pmod p\)，并会分「互素 / 不互素」两种情况处理。
0引言：群论的一个有趣应用 ⏱ 00:01
- 本讲是群论知识的一个非常有趣的应用：用群论来证明数论里一个非常重要的定理——欧拉定理。
- 欧拉定理处理的全是「数」的问题，是数论里面的结论；但事实上我们可以用群论的内容来证明它——这正是本讲要展示的东西。
- 在给出欧拉定理的具体结论以前，先要认识一个预备概念：欧拉函数。
1欧拉函数 ⏱ 00:22
1.1 例子
1.2 小结表
| \(n\) | 小于 \(n\) 且与 \(n\) 互素的正整数 | \(\varphi(n)\) |
|---|---|---|
| \(5\) | \(1, 2, 3, 4\) | \(4\) |
| \(4\) | \(1, 3\) | \(2\) |
| \(10\) | \(1, 3, 7, 9\) | \(4\) |
这三个值后面会反复用到：验证欧拉定理的例子、计算 \(7^{222} \bmod 10\) 都要靠它们。
2欧拉定理 ⏱ 02:45
2.1 用小例子理解结论
看到这里你也许会问：\(3^{4} \bmod 5\)、\(7^{4} \bmod 10\) 这种我口算就行了，为什么还需要欧拉定理？下面的例子会说明它的用处。
3应用例子：求 \(7^{222}\) 除以 \(10\) 的余数 ⏱ 05:26
把数变得更大一些、把幂次变得更大一些，欧拉定理有用的地方就显现出来了。比如要求
这已经不是口算能算出来的了。但用欧拉定理可以一下子算出来：
- 现在 \(n = 10\)，\(a = 7\)，\(\gcd(7, 10) = 1\)，且 \(\varphi(10) = 4\)。由欧拉定理：
\[ 7^{4} \equiv 1 \pmod{10}. \]
- 把指数 \(222\) 对 \(4\) 做带余除法：
\[ 222 = 4 \times 55 + 2 \quad (4 \times 55 = 220,\ 220 + 2 = 222). \]
- 于是 ⏱ 06:41
\[ 7^{222} = 7^{4 \times 55 + 2} = \bigl(7^{4}\bigr)^{55} \cdot 7^{2}. \]因为 \(7^{4} \equiv 1 \pmod{10}\)，所以 \(\bigl(7^{4}\bigr)^{55}\) 除以 \(10\) 的余数总是 \(1\)，这一部分可以「扔掉」：\[ 7^{222} \equiv 1^{55} \cdot 7^{2} = 49 \equiv 9 \pmod{10}. \]
结论：\(7^{222}\) 除以 \(10\) 的余数是 \(9\)。本来是一个很大的数，你不知道它到底是什么样子；但用欧拉定理，一下子就可以算出来——这就是欧拉定理好用的地方。
4证明思想：总览 ⏱ 07:27
先简单讲一下思想，然后再具体证明。
- 情况一：\(a < n\)，且 \(a\) 与 \(n\) 互素（互素本来就是定理的假设）；
- 情况二：\(a > n\)，且 \(a\) 与 \(n\) 互素。
- 情况一的做法：构造一个群 \(G\)，它的阶恰好等于欧拉函数值 \(\varphi(n)\)，然后利用拉格朗日定理（的推论）直接得到结论——这就是为什么说这个证明很有意思。
- 情况二的做法：想办法把它归结为情况一（对 \(a\) 除以 \(n\) 取余数）。
整个证明分三步：
- 第一步（关键）：给 \(G\) 定义一个运算，并证明 \(G\) 在这个运算下是一个群（同时确认它的单位元是 \(1\)）；
- 第二步：处理情况一（\(a < n\)）——用拉格朗日定理的推论；
- 第三步：处理情况二（\(a > n\)）——归结为余数。
课堂上先假设第一步已经完成，看看第二、三步如何迅速得出结论（第 5、6 节），最后再回头证明第一步（第 7 节）。
5第二步：情况 \(a < n\)（假设 \(G\) 已是群）⏱ 10:11
假设第一步已经证完：\(G\) 是一个群，\(|G| = \varphi(n)\)，并且它的单位元是 \(1\)（\(1 \in G\)，从前面枚举的例子也看得出单位元就是 \(1\)）。⏱ 11:08
- 若 \(a < n\) 且 \(\gcd(a, n) = 1\)，则由 \(G\) 的定义，立刻知道 \(a \in G\)。
- 把 \(a\) 看作群 \(G\) 中的元素，由拉格朗日定理的推论：
\[ a^{\varphi(n)} = a^{|G|} = e. \]
- \(G\) 的单位元是 \(1\)，而群中的「等于」就是「模 \(n\) 同余」，所以
\[ a^{\varphi(n)} \equiv 1 \pmod n. \]
所以如果 \(a\) 小于 \(n\)，结论就比较好证了——只要证明 \(G\) 是一个群就可以了。
6第三步：情况 \(a > n\)（归结为余数）⏱ 12:17
如果 \(a\) 大于 \(n\) 怎么办呢？用带余除法：
其中 \(q\) 是商，\(r\) 是 \(a\) 除以 \(n\) 的余数，余数一定在 \(0\) 和 \(n\) 之间。
- 首先 \(r \neq 0\)：若 \(r = 0\)，则 \(n \mid a\)，于是 \(a\) 与 \(n\) 有公因子 \(n\)，与「\(a\) 与 \(n\) 互素」矛盾。⏱ 13:36
- 关键：还要证明余数 \(r\) 也与 \(n\) 互素（这是一个非常重要的条件）。
证明 \(\gcd(r, n) = 1\)（点击展开）⏱ 14:06
反证。假设 \(r\) 与 \(n\) 不互素，则存在大于 \(1\) 的整数 \(d\)，使得 \(d \mid r\) 且 \(d \mid n\)。
因为 \(a = nq + r\)，而 \(d \mid n\)（从而 \(d \mid nq\)）、\(d \mid r\)，所以
这样 \(d\) 同时是 \(a\) 和 \(n\) 的因子，即 \(a\) 与 \(n\) 不互素——与定理的假设 \(\gcd(a, n) = 1\) 矛盾。
故 \(\gcd(r, n) = 1\)。
于是 \(r < n\) 且 \(r\) 与 \(n\) 互素，根据 \(G\) 的定义，立刻推出 \(r \in G\)。⏱ 16:07 既然 \(r\) 是群 \(G\) 里的元素，就可以用群论的结论（群的阶是 \(\varphi(n)\)）：
但我们想证的是 \(a^{\varphi(n)} \equiv 1 \pmod n\)，而不是 \(r\) 的。没关系——由 \(a = nq + r\)，两边同时取 \(\varphi(n)\) 次幂 ⏱ 16:40：
因为展开式中凡是出现 \(nq\) 因子的项，模 \(n\) 以后全都变为 \(0\)。于是
所以如果 \(a\) 大于 \(n\)，结论也可以证明——你只需要证明余数 \(r\) 也在群 \(G\) 里面就可以了。
7第一步：证明 \(G\) 是一个群（关键）⏱ 17:34
现在的关键点是：如何证明「小于 \(n\) 且与 \(n\) 互素的正整数的集合」是一个群？一个群需要「集合 + 运算」：集合已经有了（元素个数是 \(\varphi(n)\)，且 \(1 \in G\)），如何定义运算、如何使它成为群结构，才是需要证明的。第一步证完以后，第二步和第三步就都没有问题了。
7.1 定义运算：模 \(n\) 乘法 ⏱ 18:28
7.2 运算的合理性（封闭性）⏱ 20:46
要这么定义，首先得保证定义的运算是合理的。回顾第一讲二元运算的定义：任取两个元素，做完运算以后，结果应该还在 \(G\) 里面，这才是一个二元运算。
- \(s < n\) 没有问题——\(s\) 本来就是取余数得到的；
- 关键是：\(s\) 是否与 \(n\) 互素？若 \(s\) 确实与 \(n\) 互素，则 \(s \in G\)，运算才封闭。
证明 \(s \in G\)（即 \(\gcd(s, n) = 1\)）（点击展开）⏱ 21:20
反证。假设 \(s\) 与 \(n\) 不互素，则可以找到一个公因子；把公因子取得「特别一点」——取一个素数公因子 \(p\)（只要公因子大于 \(1\)，就总能取到素因子）：
由运算的定义，\(mk \equiv s \pmod n\)，即存在整数 \(\ell\) 使得
因为 \(p \mid s\) 且 \(p \mid n\)，所以 \(p \mid (s + \ell n) = mk\)，即 \(p\) 是 \(mk\) 的因子。
\(p\) 是素数，整除乘积 \(mk\)，则 \(p\) 必整除其中一个因子：\(p \mid m\) 或 \(p \mid k\)。
- 若 \(p \mid m\)：又 \(p \mid n\)，则 \(p\) 是 \(m\) 与 \(n\) 的公因子，于是 \(p \mid \gcd(m, n)\)。但 \(m \in G\)，\(\gcd(m, n) = 1\)，矛盾；
- 若 \(p \mid k\)：同理 \(p \mid \gcd(k, n) = 1\)，矛盾。
两种情况都矛盾，故假设不成立，\(\gcd(s, n) = 1\)。于是 \(s < n\) 且与 \(n\) 互素，\(s \in G\)。到这里才有办法说：定义的运算 \(m \cdot k = s\) 确实是合理的——基本上什么条件都得用上（\(m, k\) 都要与 \(n\) 互素）。
7.3 结合律与单位元 ⏱ 24:52
- 结合律：比较显然——用模 \(n\) 同余的算式即可验证：\((mk)\ell\) 与 \(m(k\ell)\) 模 \(n\) 的余数相同（普通乘法满足结合律，取余不改变这一点）。
- 单位元是 \(1\)：也比较显然。首先 \(1 \in G\)；其次 \(1\) 乘上任何一个 \(k \in G\)，即 \(1 \cdot k = k\)（余数就是 \(k\) 本身），左右都成立。
7.4 逆元：用 Bézout 恒等式 ⏱ 25:41
现在关键的问题就是关于逆元：如何证明任何一个元素都有逆元？任取 \(m \in G\)，即 \(m < n\) 且 \(\gcd(m, n) = 1\)。要找 \(m\) 的逆元，就是要找一个 \(k\)，使得
并且还得保证 \(k\) 确实在 \(G\) 里面（小于 \(n\) 且与 \(n\) 互素）——这些条件都得满足。
证明每个 \(m \in G\) 都有逆元（点击展开）
因为 \(\gcd(m, n) = 1\)，由 Bézout 恒等式，存在整数使得 \(mx + ny = 1\)。对 \(x\) 模 \(n\) 取余，可以选取 \(k\) 满足 \(0 < k < n\)，以及某个整数 \(t\)，使得
（这就是对第一个系数 \(x\) 加的限制：让它落在小于 \(n\) 的范围里，因为我们想找的逆元必须在 \(G\) 里。）
模 \(n\) 看这个式子：\(nt\) 这一部分模 \(n\) 是 \(0\)，所以立刻得到
还差最后一个条件：\(k\) 要与 \(n\) 互素，才能保证 \(k \in G\)。仍用反证：若有素数 \(p\) 满足 \(p \mid k\) 且 \(p \mid n\)，则由 \(mk + nt = 1\) 知 \(p\) 整除左边两项，从而 \(p \mid 1\)——不可能。故 \(\gcd(k, n) = 1\)。
于是 \(k\) 既满足「与 \(m\) 相乘等于单位元」，又是小于 \(n\) 且与 \(n\) 互素的正整数，即 \(k \in G\)。所以从任何一个 \(m\) 出发，都可以把它的逆元找到：\(m^{-1} = k\)。
7.5 收拢：欧拉定理的完整证明 ⏱ 30:36
欧拉定理完整证明（串讲，点击展开）
- 令 \(G = \{\, m \mid 1 \le m < n,\ \gcd(m, n) = 1 \,\}\)，定义 \(m \cdot k\) 为 \(mk\) 模 \(n\) 的余数。验证运算合理（封闭）、结合律成立、单位元为 \(1\)、每个元素有逆元（Bézout）——故 \(G\) 是群，\(|G| = \varphi(n)\)。
- 若 \(a < n\) 且 \(\gcd(a, n) = 1\)：则 \(a \in G\)，由拉格朗日定理的推论 \(a^{|G|} = e\)，即 \(a^{\varphi(n)} \equiv 1 \pmod n\)。
- 若 \(a > n\) 且 \(\gcd(a, n) = 1\)：设 \(a = nq + r\)，\(0 < r < n\)。先证 \(\gcd(r, n) = 1\)（否则与 \(\gcd(a, n) = 1\) 矛盾），故 \(r \in G\)，于是 \(r^{\varphi(n)} \equiv 1 \pmod n\)；再证 \(a^{\varphi(n)} = (nq + r)^{\varphi(n)} \equiv r^{\varphi(n)} \pmod n\)，从而 \(a^{\varphi(n)} \equiv 1 \pmod n\)。
两种情况都成立，欧拉定理证毕。本来都是数论里面的东西，却可以用群的思想来证明——这个证明很有意思。当然它还有其他的证明方法，有兴趣可以了解一下。
8推论：费马小定理 ⏱ 31:05
课本好像也给了费马小定理。它其实是欧拉定理的一个比较简单的推论，直接推论就很快了。
证明（分两种情况，点击展开）⏱ 31:47
情况一：\(a\) 与 \(p\) 互素。由欧拉定理，考虑所有小于 \(p\) 且与 \(p\) 互素的元素组成的群，直接得到
因为 \(p\) 是素数，小于 \(p\) 且与 \(p\) 互素的元素就是 \(1, 2, \dots, p-1\)，共 \(p - 1\) 个，所以 \(\varphi(p) = p - 1\)。于是
两边同乘以 \(a\)，就得到
情况二：\(a\) 与 \(p\) 不互素。⏱ 33:32因为 \(p\) 是素数，\(a\) 与 \(p\) 不互素就意味着 \(p \mid a\)，即对某个整数 \(m\) 有 \(a = pm\)。于是
两边模 \(p\) 都是 \(0\)（「两边都是零了」），所以 \(a^{p} \equiv a \pmod p\) 同样成立。
两种情况合起来，费马小定理得证。
★重点回顾
⚠易错点提醒
- 忽略互素条件：欧拉定理要求 \(\gcd(a, n) = 1\)。不互素时结论一般不成立（如 \(2^{2} = 4 \equiv 0 \pmod 4\)，不是 \(1\)）。
- 指数处理出错：用欧拉定理化简大指数时，要把指数对 \(\varphi(n)\) 做带余除法：\(a^{m} = a^{\varphi(n) q + r} \equiv a^{r} \pmod n\)。例如 \(222 = 4 \times 55 + 2\)，不要漏掉余下的 \(7^{2}\)。
- 忘记验证运算的合理性：定义 \(m \cdot k = mk \bmod n\) 后，必须证明结果 \(s\) 仍在 \(G\) 中——\(s < n\) 显然，但「\(s\) 与 \(n\) 互素」需要专门证明（素公因子反证法），这是最容易漏掉的一步。
- 混淆 \(a\) 与余数 \(r\)：当 \(a > n\) 时，属于群 \(G\) 的是余数 \(r\) 而不是 \(a\) 本身；要先证 \(\gcd(r, n) = 1\)，再用 \(a^{\varphi(n)} \equiv r^{\varphi(n)} \pmod n\) 回到 \(a\)。
- 费马小定理忘记分情况：\(a\) 与 \(p\) 不互素时不能直接用欧拉定理；此时利用 \(p\) 是素数得 \(p \mid a\)，两边模 \(p\) 同为 \(0\)。
- 工具混淆：本讲用到的是「拉格朗日定理的推论」（有限群中任一元素的群阶次幂等于单位元），不要与拉格朗日定理本身（子群的阶整除群的阶）混为一谈。
✎自测与作业
- 按定义计算：\(\varphi(12)\)、\(\varphi(7)\)、\(\varphi(9)\)（逐一枚举小于 \(n\) 且与 \(n\) 互素的正整数）。
- 用欧拉定理求 \(3^{100}\) 除以 \(7\) 的余数。（提示：\(\varphi(7) = 6\)，\(100 = 6 \times 16 + 4\)，再算 \(3^{4} \bmod 7\)。）
- （课上作业）证明费马小定理：若 \(p\) 是素数，则对任意自然数 \(a\)，\(a^{p} \equiv a \pmod p\)。要求分「\(a\) 与 \(p\) 互素 / 不互素」两种情况完成。
- 把第 7 节的细节补完整：用同余的算式详细验证 \(G\) 上的乘法满足结合律，即 \((m \cdot k) \cdot \ell = m \cdot (k \cdot \ell)\)。
- 思考：逆元的证明中为什么要单独验证「\(k\) 与 \(n\) 互素」？如果跳过这一步，群公理的哪一条会出问题？