欧拉定理

1. 定理表述

设 $m$ 是大于 $1$ 的正整数。如果整数 $a$ 与 $m$ 互素（即 $\gcd (a,m)=1$），则： $a^{\phi (m)}\equiv 1(\mathrm{mod}m)$ 其中 $\phi (m)$ 是 欧拉函数，表示小于等于 $m$ 且与 $m$ 互素的正整数个数。

2. 证明思路

利用 简化剩余系 (RRS) 的性质进行证明：

1. 设 $\{r_1,r_2,\dots ,r_{\phi (m)}\}$ 是模 $m$ 的一个简化剩余系。
2. 因为 $(a,m)=1$，所以 $\{a{r}_1,a{r}_2,\dots ,a{r}_{\phi (m)}\}$ 也是模 $m$ 的一个简化剩余系（只是顺序不同）。
3. 将两个集合中的所有元素分别相乘，结果在模 $m$ 下同余： ${\prod }_{i=1}^{\phi (m)}(a{r}_i)\equiv {\prod }_{i=1}^{\phi (m)}{r}_i(\mathrm{mod}m)$
4. 提取 $a$： $a^{\phi (m)}\cdot \left({\prod }_{i=1}^{\phi (m)}{r}_i\right)\equiv {\prod }_{i=1}^{\phi (m)}{r}_i(\mathrm{mod}m)$
5. 由于 $r_i$ 与 $m$ 互素，它们的乘积也与 $m$ 互素，根据消去律消去乘积项，即得证。

3. 重要推论

3.1 费马小定理

当模数 $m$ 为素数 $p$ 时，$\phi (p)=p-1$。此时欧拉定理退化为： $a^{p-1}\equiv 1(\mathrm{mod}p)(\text{若 }p\nmid a)$ 这是欧拉定理的特例。

3.2 模逆元的计算

如果 $(a,m)=1$，则 $a$ 的模 $m$ 逆元为： $a^{-1}\equiv a^{\phi (m)-1}(\mathrm{mod}m)$ 这提供了一种不使用扩展欧几里得算法求逆元的方法（虽然通常效率较低，除非已知 $\phi (m)$）。

4. 核心应用：RSA 算法

RSA 公钥密码体制的解密过程正确性直接依赖于欧拉定理。

• 密钥满足：$e\cdot d\equiv 1(\mathrm{mod}\phi (n))$，即 $ed=k\phi (n)+1$。
• 解密验证： $c^d\equiv (m^e{)}^d\equiv m^{ed}\equiv m^{k\phi (n)+1}\equiv (m^{\phi (n)}{)}^k\cdot m\equiv 1^k\cdot m\equiv m(\mathrm{mod}n)$ (注：上述推导在 $(m,n)=1$ 时直接成立；不互素时需额外证明，但结论依然成立)。

---

计算示例

计算 $7^{100}(\mathrm{mod}10)$。

1. 模数 $m=10$，$\phi (10)=10(1-\frac{1}{2})(1-\frac{1}{5})=4$。
2. 底数 $a=7$，$(7,10)=1$，满足条件。
3. 由欧拉定理：$7^4\equiv 1(\mathrm{mod}10)$。
4. 指数 $100=4\times 25$。
5. $7^{100}=(7^4{)}^{25}\equiv 1^{25}\equiv 1(\mathrm{mod}10)$。