欧拉函数 φ(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..12 里有几个与 12 互质？12 = 2²·3，蓝图：把含质因子 2 或 3 的数全划掉，幸存者就是互质的——每个质因子按比例划，正是 φ(n) = n·∏(1−1/p)

它解锁了什么

性质：φ(p) = p−1；φ(p^k) = p^k − p^(k−1)；gcd(a,b)=1 时 φ(ab) = φ(a)·φ(b)（积性）。
欧拉定理：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) 定周期。