欧拉函数 φ(n)
数学与数论 · 互质计数 · 欧拉定理的钥匙
数一数：谁和 n 互质
欧拉函数 φ(n) = 1..n 中与 n 互质的个数（1 也算）。比如 φ(12)：12 = 2²·3，凡是含质因子 2 或 3 的数都和 12 有公因子——把它们划掉，幸存者 {1, 5, 7, 11} 就是答案，φ(12) = 4。
按比例划掉：公式的筛法直观
2 的倍数每 2 个占 1 个——划掉后剩 n·(1−1/2)；3 的倍数每 3 个占 1 个，但其中一半已被 2 划过，新划的按比例正好再乘 (1−1/3)。每个不同质因子各打一次折，就是 φ(n) = n·∏(1−1/p)：12·(1/2)·(2/3) = 4。点「下一步」看网格逐质因子划格（红闪 → 灰）、幸存者变绿，vars 里同步 res 记账。右侧代码是试除版 phi(n)，随每一步同步高亮。
1
2
3
4
5
6
7
8
9
10
11
12
数 1..12 里有几个与 12 互质？12 = 2²·3，蓝图：把含质因子 2 或 3 的数全划掉，幸存者就是互质的——每个质因子按比例划，正是 φ(n) = n·∏(1−1/p)
1function phi(n: number): number {
2 let res = n; // 从 n 出发记账
3 for (let p = 2; p * p <= n; p++) {
4 if (n % p !== 0) continue; // 试除：找质因子
5 res -= res / p; // 乘 (1 − 1/p)：按比例划掉
6 while (n % p === 0) n /= p; // 除尽这个质因子
7 }
8 if (n > 1) res -= res / n; // 还剩一个大质因子
9 return res; // 幸存者个数 = φ(n)
10}
n12 = 2²·3
目标φ(12) = 与 12 互质的个数
res12
1 / 7
它解锁了什么
性质：φ(p) = p−1；φ(p^k) = p^k − p^(k−1)；gcd(a,b)=1 时 φ(ab) = φ(a)·φ(b)（积性）。
欧拉定理：gcd(a,n)=1 ⟹
指数打折：算 a^k mod n 时指数可先对 φ(n) 取模，再交给快速幂。
批量求 φ：线性筛可顺路算出 1..N 的全部 φ 值，O(N)。
欧拉定理：gcd(a,n)=1 ⟹
a^φ(n) ≡ 1 (mod n)——费马小定理（n 为质数时 φ=n−1）的推广。指数打折：算 a^k mod n 时指数可先对 φ(n) 取模，再交给快速幂。
批量求 φ：线性筛可顺路算出 1..N 的全部 φ 值，O(N)。
RSA 里它是真正的主角：n = p·q 公开，φ(n) = (p−1)(q−1) 只有知道分解的人才算得出——私钥 d ≡ e⁻¹ (mod φ(n))（扩展欧几里得求逆），加解密是快速幂的模幂，CRT再把运算拆到 mod p、mod q 提速四倍。数论这条线的角色到齐了：筛法产质数、gcd/扩欧管互质与逆元、快速幂做模幂、CRT 合并、φ(n) 定周期。