在线欧拉函数计算器

欧拉函数 φ(n) 统计 1 到 n 中与 n 互质（最大公约数为 1）的整数个数。计算不需要逐个验证：把 n 质因数分解后，φ(n) = n × ∏(1 − 1/p)，只需对 n 的每个不同质因数 p 乘一次 (1 − 1/p)。

φ 函数是 RSA 加密的数学基石：欧拉定理指出，若 gcd(a, n) = 1，则 a^φ(n) ≡ 1 (mod n)，RSA 的加解密互逆正是依赖这条定理。n ≤ 500 时工具会列出全部互素数清单，便于验证与学习。

欧拉函数 φ(n) 计数「1 到 n 中与 n 互质的整数个数」，1763 年欧拉在证明费马小定理的推广时引入。它是积性函数：只要 gcd(m,n)=1 就有 φ(mn) = φ(m)φ(n)——这条性质把任意合数的计算化归到质数幂，再配合公式 φ(pᵏ) = pᵏ−pᵏ⁻¹，任何数的 φ 值都能从质因数分解一步得出。

欧拉定理 a^φ(n) ≡ 1 (mod n)（当 gcd(a,n)=1）是 φ 函数的最高光时刻：它是费马小定理的直接推广（n 为质数时 φ(n) = n−1），也是 RSA 加密的数学地基——RSA 选两个大质数 p、q，公开 n = pq，私钥构造依赖 φ(n) = (p−1)(q−1)；攻击者要破解就必须在不知道分解的情况下求 φ(n)，而这被证明与分解 n 等价困难。你每一次 HTTPS 连接背后，都有 φ 函数在站岗。

φ(n) 的「平均行为」是解析数论的经典结果：前 N 项之和约为 3N²/π² ≈ 0.304N²，意味着随机两个整数互质的概率是 6/π² ≈ 61%——圆周率就这样毫无征兆地出现在互质问题里。φ 的取值分布极不规则（奇数几乎不可能是 φ 值，除 φ(1)=φ(2)=1 外 φ(n) 恒为偶数），「哪些数永远不是 φ 值」本身也是未完全解决的问题。