概念

欧拉定理

用欧拉函数 φ(n) 把费马小定理推广到合数模，a^φ(n) ≡ 1 (mod n)，RSA 加密依赖它。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

欧拉定理初等数论

01定义

欧拉函数

\varphi(n)

计数不超过

n

且互素的正整数。欧拉定理

a^{\varphi(n)}\equiv 1\pmod n

（

\gcd(a,n)=1

）把费马小定理推广到任意合数模——RSA 加密解密的正确性全靠它。

模 n 单位群：φ(n) 个可逆剩余类

$\varphi(n)=n\prod_{p\mid n}(1-\frac{1}{p})$ ：容斥原理逐素因子筛除； $\varphi$ 乘性（ $\gcd(m,n)=1$ 时 $\varphi(mn)=\varphi(m)\varphi(n)$ ）使计算归约到素数幂。

取 $n=pq$ ，公钥 $e$ 、私钥 $d$ 满足 $ed\equiv 1\pmod{\varphi(n)}$ ；欧拉定理保证 $(m^e)^d\equiv m$ ——加密解密互逆的数学依据。

若存在阶恰为 $\varphi(n)$ 的元素（原根），单位群为循环群；素数模必有原根——离散对数与 Diffie-Hellman 密钥交换的根基。

a^{\varphi(n)}\equiv 1\pmod n\quad(\gcd(a,n)=1)

欧拉 1736 年证明费马小定理的推广，1760 年代定义 φ 函数；高斯《算术研究》系统发展剩余类群；RSA 1977 年让这一定理走进每张银行卡。

RSA 公钥密码、欧拉函数在群论计数（循环子群数）中的应用、原根构造伪随机序列、中国剩余定理组合的密码协议。

a^φ(n) ≡ 1 (mod n)：模乘循环a 与 n 互素时，幂序列沿模环走 φ(n) 步恰好回到 1

n 模数10a 底数3