欧拉函数

设想从 1 到 n 这些数，问其中有多少个与 n 互不相干 — 即与 n 没有公因数。欧拉函数所度量的正是这个计数：它统计该范围内与 n 互素的整数个数。

记作 φ(n)（希腊字母 phi），它是满足 1 ≤ k ≤ n 且 gcd(k, n) = 1 的整数 k 的个数。对素数 p，每个比它小的正数都与它互素，所以 φ(p) = p − 1。该函数对互素的自变量是积性的 — 当 gcd(m, n) = 1 时 φ(m n) = φ(m) φ(n) — 而对素数幂，φ(p^k) = p^k − p^(k−1)。把这些结合起来，便得到由素因数分解给出的公式：φ(n) = n 乘以所有整除 n 的素数 p 的 (1 − 1/p) 之积。

欧拉函数是欧拉定理 a^(φ(n)) ≡ 1 (mod n)（a 与 n 互素）的支柱，而后者又是 RSA 密码体制的基础。一个常见的绊脚石：当两个自变量有公因数时 φ 并非积性 — φ(2 乘以 2) = φ(4) = 2，而不是 φ(2) 乘以 φ(2) = 1 — 所以积性这一性质严格要求自变量互素。