这是数论四大定理系列的第三篇。欧拉定理（Euler’s Theorem）是费马小定理的完全升级版，它解决了模数 $n$ 不是质数时的同余问题。
在上一讲中，我们学习了费马小定理：
12月28日 21:00但这留下了一个遗憾：如果模数 $n$ 不是质数（比如 $n=10$ 或 $n=100$），我们还能找到类似的周期规律吗？
伟大的数学家欧拉（Leonhard Euler）站了出来，他给出的答案不仅解决了这个问题，还将费马小定理包含其中，成为了数论中的一座丰碑。
一、 必修前置技能：欧拉函数 $\varphi(n)$
在介绍定理前，我们需要先认识一个新朋友——欧拉函数，符号写作 $\varphi(n)$（读作 phi）。
1. 什么是 $\varphi(n)$？
$\varphi(n)$ 表示的是在 $1 \sim n$ 的自然数中，与 $n$ 互质的数的个数。
2. 怎么算？
如果是质数：
如果 $n$ 是质数 $p$，那么 $1 \sim p-1$ 的所有数都和它互质。
$$ \varphi(p) = p – 1 $$
如果是合数：
我们需要用到公式。设 $n$ 的质因数分解为 $n = p_1^{k_1} p_2^{k_2} \cdots$，则：
$$ \varphi(n) = n \times \left(1 – \dfrac{1}{p_1}\right) \times \left(1 – \dfrac{1}{p_2}\right) \times \cdots $$
实战计算 $\varphi(10)$：
$10$ 的质因数是 $2$ 和 $5$。
$$ \varphi(10) = 10 \times \left(1 – \dfrac{1}{2}\right) \times \left(1 – \dfrac{1}{5}\right) = 10 \times \dfrac{1}{2} \times \dfrac{4}{5} = 4 $$
验证：$1 \sim 10$ 中与 $10$ 互质的数是 1, 3, 7, 9，确实是 $4$ 个。
二、 欧拉定理登场
有了 $\varphi(n)$ 这个工具，欧拉定理的内容就非常简洁优美了：
人话翻译：
只要 $a$ 和 $n$ 互质，不管 $n$ 是什么数（质数或合数），$a$ 的次幂除以 $n$ 的余数都是有周期的，这个周期就是 $\varphi(n)$。
它是费马小定理的一般情况
当 $n$ 是质数 $p$ 时，$\varphi(n) = p-1$。
公式就变成了 $a^{p-1} \equiv 1 \pmod p$。
费马小定理只是欧拉定理的一个特殊情况。
三、 实例演示
为了理解定理，我们用 $\varphi(10)=4$ 的例子。
令 $n=10$，$a=3$（$3$ 与 $10$ 互质）。
根据定理，应该有 $3^{\varphi(10)} = 3^4 \equiv 1 \pmod{10}$。
1. 构造“缩系”
我们找出 $1 \sim 10$ 中与 $10$ 互质的所有数，即$1$、$3$、$7$、$9$，将这组数记作$ S = \{1, 3, 7, 9\} $，为什么是$4$个数呢，因为$\varphi(10)=4$
注：这个集合在数论中叫简化剩余系（或缩系）。
2. 乘法变换
把 $S$ 中的每个数都乘以 $a=3$，得到新的一组数 $S’$：
$$ S’ = \{1\times 3, 3\times 3, 7\times 3, 9\times 3\} = \{3, 9, 21, 27\} $$
3. 取模观察
将 $S’$ 中的数对 $10$ 取模：
$3 \equiv 3 \pmod{10}$
$9 \equiv 9 \pmod{10}$
$21 \equiv 1 \pmod{10}$
$27 \equiv 7 \pmod{10}$
得到的余数是 $\{3, 9, 1, 7\}$。
神奇的现象出现了：它和原来的 $\{1, 3, 7, 9\}$ 完全一样，只是顺序变了！
4. 为什么会这样？（反证法）
假设 $S$ 中有两个不同的数 $m, n$，乘以 $a$ 后同余：
$$ a \times m \equiv a \times n \pmod{10} $$
$$ a(m – n) \equiv 0 \pmod{10} $$
因为 $\gcd(a, 10) = 1$，所以 $10$ 必须整除 $(m-n)$。
但 $m, n$ 都是小于 $10$ 的不同的数，差值的绝对值小于 $10$，不可能被 $10$ 整除。
矛盾！
所以，变换后的数模 $10$ 互不相同，且都与 $10$ 互质。它们只能是原集合的重新排列。
5. 整体相乘
既然两个集合的元素模 $10$ 是一样的，那么它们的乘积也模 $10$ 同余。
$$ (3\times 1) \cdot (3\times 3) \cdot (3\times 7) \cdot (3\times 9) \equiv 1 \cdot 3 \cdot 7 \cdot 9 \pmod{10} $$
提取左边的公因数 $3$（一共 $\varphi(10)=4$ 个）：
$$ 3^4 \cdot (1 \cdot 3 \cdot 7 \cdot 9) \equiv (1 \cdot 3 \cdot 7 \cdot 9) \pmod{10} $$
两边消去 $(1 \cdot 3 \cdot 7 \cdot 9)$（因为它与 $10$ 互质）：
$$ 3^4 \equiv 1 \pmod{10} $$
得证！
四、一般情况的严格证明
明白了上面的例子，我们将其推广到任意 $n$。以下是严谨的数学证明：
$1$ 至 $n$ 中与 $n$ 互质的自然数的个数是 $\varphi(n)$ 个，记这 $\varphi(n)$ 个数为 $a_1, a_2, a_3, \cdots, a_{\varphi(n)}$。
这 $\varphi(n)$ 个数除以 $n$ 的余数显然互不相同（因为它们都小于 $n$ 且不同）。
我们将这些数同时乘以 $a$，得到：
$a\times a_1, a\times a_2, a\times a_3, \cdots, a\times a_{\varphi(n)}$。
第一步：证明变换后的数模 $n$ 互不相同
若 $a\times a_m$ 和 $a\times a_n$ 模 $n$ 同余，即 $a\times a_m \equiv a\times a_n \pmod n$。
则 $n \mid (a\times a_m – a\times a_n) \implies n \mid a(a_m – a_n)$。
因为已知 $(a, n) = 1$，所以必然有 $n \mid (a_m – a_n)$。
但$a_m, a_n$ 都是小于 $n$ 的不同的正整数，其差不可能被 $n$ 整除，矛盾。
第二步：得出余数相等的结论
所以 $a\times a_1, a\times a_2, \cdots, a\times a_{\varphi(n)}$ 除以 $n$ 的余数互不相同，且每一个余数都在 $1 \sim n$ 之间并与 $n$ 互质。
因此，这些余数的集合只能是 $a_1, a_2, \cdots, a_{\varphi(n)}$ 的一种重新排列。
第三步：乘积取模
既然两个集合的元素模 $n$ 是一样的，那么它们的乘积也模 $n$ 同余：
$$ (a\times a_1)\cdot(a\times a_2)\cdots(a\times a_{\varphi(n)}) \equiv a_1\cdot a_2\cdots a_{\varphi(n)} \pmod n $$
提取左边的 $a$，一共有 $\varphi(n)$ 个 $a$：
$$ a^{\varphi(n)} \cdot (a_1\cdot a_2\cdots a_{\varphi(n)}) \equiv (a_1\cdot a_2\cdots a_{\varphi(n)}) \pmod n $$
第四步：消去公因子
令 $K = a_1\cdot a_2\cdots a_{\varphi(n)}$。因为每个 $a_i$ 都与 $n$ 互质，所以 $K$ 也与 $n$ 互质，即 $(K, n) = 1$。
根据同余式的性质，我们可以两边同时约去 $K$：
$$ a^{\varphi(n)} \equiv 1 \pmod n $$
证毕。
四、 习题实战：指数爆炸怎么办？
欧拉定理的核心应用依然是降幂，但步骤多了一步：先算 $\varphi(n)$。
公式：$a^b \equiv a^{b \pmod{\varphi(n)}} \pmod n$。
入门题
题目：求 $7^{2026}$ 的个位数（即求模 $10$ 的余数）。
解析：
- 看模数：模数为 $10$，先算 $\varphi(10)$。
$\varphi(10) = 4$。 - 看底数：$\gcd(7, 10)=1$，满足欧拉定理条件。
所以 $7^4 \equiv 1 \pmod{10}$。 - 降指数：
$2026 \div 4 = 506 \dots 2$。
$$ 7^{2026} \equiv 7^2 \pmod{10} $$ - 计算：
$7^2 = 49 \equiv 9 \pmod{10}$。
答案：个位数是 9。
进阶题
题目：求 $2^{103}$ 除以 $25$ 的余数。
解析：
- 算 $\varphi(n)$：
$n=25=5^2$。
$\varphi(25) = 25 \times (1 – \dfrac{1}{5}) = 20$。
这意味着 $2^{20} \equiv 1 \pmod{25}$。 - 降指数：
$103 \div 20 = 5 \dots 3$。
$$ 2^{103} = (2^{20})^5 \cdot 2^3 \equiv 1^5 \cdot 8 \equiv 8 \pmod{25} $$
答案：8。
易错点提醒
题目：求 $2^{10}$ 除以 $10$ 的余数。
陷阱：
很多同学会直接算 $\varphi(10)=4$，然后说 $2^{10} \equiv 2^2 = 4$。这是错的！
原因：$\gcd(2, 10) = 2 \neq 1$。底数与模数不互质，不能直接用欧拉定理。
正确做法：
这种不互质的情况，需要观察规律或拆分。
$2^{10} = 1024$，除以 $10$ 余 $4$。
下一讲，我们将介绍数论四大定理的最后一块拼图，也是用来解同余方程的利器：威尔逊定理。
暂无评论内容