欧拉定理

概述

欧拉定理（Euler’s Theorem）：若 $a$ 和 $n$ 互素（即 $\gcd (a,n)=1$），则 $a^{\phi (n)}\equiv 1(\mathrm{mod}n)$，其中 $\phi (n)$ 是欧拉函数，表示不超过 $n$ 且与 $n$ 互素的正整数个数。

定理陈述

形式化陈述

欧拉定理：设 $n$ 为正整数，$a$ 为整数。若 $\gcd (a,n)=1$，则： $a^{\phi (n)}\equiv 1(\mathrm{mod}n)$

其中 $\phi (n)$ 是欧拉函数（Euler’s totient function），定义为： $\phi (n)=|\{k\in {\mathbb{Z}}^{+}:1\le k\le n,\gcd (k,n)=1\}|$

特例——费马小定理：当 $n=p$ 为素数时，$\phi (p)=p-1$，欧拉定理退化为： $a^{p-1}\equiv 1(\mathrm{mod}p),\text{当 }\gcd (a,p)=1$

前置知识：欧拉函数 $\phi (n)$

欧拉函数的性质

• $\phi (1)=1$
• 若 $p$ 为素数，$\phi (p)=p-1$
• 若 $p$ 为素数，$\phi (p^k)=p^k-p^{k-1}=p^{k-1}(p-1)$
• 乘性函数：若 $\gcd (m,n)=1$，则 $\phi (mn)=\phi (m)\cdot \phi (n)$
• 对 $n=p_1^{k_1}{p}_2^{k_2}\cdots p_r^{k_r}$（素因数分解）： $\phi (n)=n{\prod }_{i=1}^r\left(1-\frac{1}{p_i}\right)$

证明概要

证明思路（群论方法）

欧拉定理的证明利用了模 $n$ 剩余类乘法群的代数结构，这是数论与群论的经典交汇点。

步骤1：构造模 $n$ 的简化剩余系

定义模 $n$ 的简化剩余系（reduced residue system）： ${\mathbb{Z}}_n^{\ast }=\{[a{]}_n:\gcd (a,n)=1\}$

即所有与 $n$ 互素的模 $n$ 剩余类构成的集合。${\mathbb{Z}}_n^{\ast }$ 中恰好有 $\phi (n)$ 个元素。

步骤2：验证 ${\mathbb{Z}}_n^{\ast }$ 构成乘法群

• 封闭性：若 $\gcd (a,n)=1$ 且 $\gcd (b,n)=1$，则 $\gcd (ab,n)=1$
• 结合律：整数乘法满足结合律，自然传递到剩余类乘法
• 单位元：$[1{]}_n$ 是单位元
• 逆元存在：若 $\gcd (a,n)=1$，由贝祖定理，存在 $b$ 使得 $ab+kn=1$，即 $[a{]}_n\cdot [b{]}_n=[1{]}_n$

因此 $({\mathbb{Z}}_n^{\ast },\cdot )$ 是一个阶为 $\phi (n)$ 的有限群。

步骤3：应用拉格朗日定理

由群论中的拉格朗日定理（Lagrange’s Theorem）：有限群中任意元素的阶整除群的阶。

• 元素 $[a{]}_n$ 在群 ${\mathbb{Z}}_n^{\ast }$ 中的阶是满足 $a^k\equiv 1(\mathrm{mod}n)$ 的最小正整数 $k$
• 由拉格朗日定理，$k\mid \phi (n)$
• 因此 $\phi (n)=k\cdot q$（某正整数 $q$）
• $a^{\phi (n)}=a^{kq}=(a^k{)}^q\equiv 1^q=1(\mathrm{mod}n)$

步骤4：等价证明（不依赖群论）

也可以用更初等的方式证明：

1. 设 $r_1,r_2,\dots ,r_{\phi (n)}$ 是模 $n$ 的简化剩余系
2. 由于 $\gcd (a,n)=1$，$a{r}_1,a{r}_2,\dots ,a{r}_{\phi (n)}$ 也是模 $n$ 的简化剩余系（互不相同且都与 $n$ 互素）
3. 因此 ${\prod }_{i=1}^{\phi (n)}{r}_i\equiv {\prod }_{i=1}^{\phi (n)}(a{r}_i)=a^{\phi (n)}{\prod }_{i=1}^{\phi (n)}{r}_i(\mathrm{mod}n)$
4. 由于 $\gcd (\prod r_i,n)=1$，两边消去 $\prod r_i$，得 $a^{\phi (n)}\equiv 1(\mathrm{mod}n)$

参考资源：

• LibreTexts抽象代数教材（Fermat和Euler定理）：https://math.libretexts.org/Bookshelves/Abstract_and_Geometric_Algebra/Abstract_Algebra%3A_Theory_and_Applications_(Judson)/06%3A_Cosets_and_Lagrange’s_Theorem/6.03%3A_Fermat’s_and_Euler’s_Theorems

关键推论

• 费马小定理：欧拉定理在 $n=p$（素数）时的特例
• 模逆元的计算：$a^{-1}\equiv a^{\phi (n)-1}(\mathrm{mod}n)$，当 $\gcd (a,n)=1$
• RSA密码系统的基础：欧拉定理是RSA加密/解密正确性的数学基石
• 阶的性质：$a$ 模 $n$ 的阶（满足 $a^k\equiv 1(\mathrm{mod}n)$ 的最小正整数 $k$）整除 $\phi (n)$

应用场景

在算法导论（CLRS）Ch31数论算法中的具体应用：

1. RSA密码系统：欧拉定理直接保证了RSA解密的正确性——加密后再解密能恢复原始消息
2. 大数模幂运算：利用 $a^{\phi (n)}\equiv 1(\mathrm{mod}n)$ 化简大指数运算，如计算 $a^b\mathrm{mod}n$ 时可先对指数取模 $\phi (n)$
3. 模运算：欧拉定理是模运算理论的核心结果之一，连接了数论与代数结构
4. 原根：原根的存在性与欧拉函数密切相关——$g$ 是模 $n$ 的原根当且仅当 $g$ 的阶为 $\phi (n)$

参见

• 模运算
• 费马小定理
• 欧拉函数
• 贝祖定理
• 公钥密码学
• 模逆元
• 原根