欧拉函数详解
写下 1 到 10,划掉每个与 10 有公因数的数。剩下四个:1、3、7 和 9。这个个数 φ(10) = 4 就是欧拉函数,它是数论中最常用的函数之一,从分数和钟表一直用到保护网上支付的加密。
统计互素的数
两个数的最大公因数为 1 时,称它们互素。φ(n) 统计 1 到 n 中满足 gcd(k, n) = 1 的 k:φ(9) = 6,φ(10) = 4,φ(12) = 4,φ(1) = 1。同一个个数会在许多地方出现。它是 0 到 1 之间已经是最简分数的 k/n 的个数,是能让指针走遍 n 小时钟面上每一个小时的步长的个数,也是模 n 有逆元、从而使 k × x ≡ 1 (mod n) 有解的 k 的个数。
乘积公式
如果整除 n 的素数是 p₁、p₂ …,那么 φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × …。原因是一个筛法。所有数中有一半是偶数,所以去掉 2 的倍数后剩下 1 − 1/2;剩下的数中每三个有一个是 3 的倍数,依此类推。根据中国剩余定理,不同素数对应的条件相互独立,所以这些比例直接相乘。对于 100 = 2² × 5²,得到 100 × 1/2 × 4/5 = 40。另外两个性质以另一种形式给出同样的结果:φ(p^k) = p^(k−1)(p − 1),以及当 m 与 n 互素时 φ(mn) = φ(m) φ(n),所以 φ(100) = φ(4) × φ(25) = 2 × 20 = 40。
欧拉定理
费马在 1640 年注意到,对素数 p 和任何不被 p 整除的 a,有 a^(p−1) ≡ 1 (mod p)。欧拉证明了一般形式,并于 1763 年发表:只要 gcd(a, n) = 1,就有 a^φ(n) ≡ 1 (mod n)。证明很短。把与 n 互素的 φ(n) 个数都乘以 a;这些乘积仍与 n 互素,而且模 n 两两不同,所以它们只是同一组数换了顺序,比较两个连乘积就剩下 a^φ(n) ≡ 1。对某个 a 成立的最小指数是它的阶,阶总是整除 φ(n);对所有 a 同时成立的最小指数是卡迈克尔函数 λ(n)。对于 561 = 3 × 11 × 17,λ(561) = 80 整除 560,所以尽管 561 不是素数,对每个与 561 互素的 a 都有 a^560 ≡ 1 (mod 561)。它是最小的卡迈克尔数,也是费马检验本身无法证明一个数是素数的原因。
高斯的因数和与平均值
把 n 的所有因数 d 的 φ(d) 加起来,总会回到 n:对 12 来说,φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12。高斯在 1801 年的《算术研究》中证明了这一点;把分数 1/12、2/12 … 12/12 化成最简分数并按分母分类,就能看出来。平均来说,φ(k) 约为 0.61 k:φ(k)/k 的平均值趋于 6/π² ≈ 0.6079,这也是随机取两个整数互素的概率;φ(1) + … + φ(N) 则接近 3N²/π²。N = 1,000 时总和为 304,192,而 3N²/π² ≈ 303,964。
永远不会出现的值
从 3 起,每个 n 的 φ(n) 都是偶数,因为与 n 互素的数成对出现:k 和 n − k。也不是每个偶数都是 φ 的值:14、26、34、38 和 50 是最早几个永远不会出现的值,而 24 是从 35 到 90 共十个不同数的函数值。找出它们是有限的搜索,因为对每个整除 n 的素数 p,p − 1 必须整除 φ(n)。1907 年,罗伯特·卡迈克尔断言没有哪个值恰好只出现一次。他的证明是错的,这个论断至今悬而未决,任何例外都必须大于 10^(10^10)。D. H. 莱默在 1932 年问道,对合数 n,φ(n) 能否整除 n − 1;目前还没有找到任何例子。
RSA 中的欧拉函数
RSA 选取两个大素数 p 和 q,公开 n = pq 和一个指数 e。由于 φ(n) = (p − 1)(q − 1),谁能分解 n,谁就能算出 φ(n),进而算出满足 e × d ≡ 1 (mod φ(n)) 的私钥指数 d;欧拉定理再保证 (m^e)^d ≡ m (mod n)。在教科书例子 n = 3233 = 61 × 53 中,φ(n) = 3,120,e = 17,d = 2,753。许多实现改用 λ(n) = lcm(p − 1, q − 1),这里是 780,得到更小的 d = 413。对于 600 位的 RSA 模数,计算 φ(n) 和分解它一样难:由 n 和 φ(n) 只需开一次平方根就能求出两个素数。
动手探索
打开计算器,输入任何不超过 10^18 的 n,即可看到 φ(n) 以及它的素因数和公式。n 不超过 500 时会画出 1 到 n,互素的数是实心的,其余的数按它们与 n 共有的最小素数着色,乘积公式就变成了一个可以数出来的筛子。选一个数 a 来验证欧拉定理,切换到“图表”查看 100,000 以内的 φ(k),素数都落在直线 φ(p) = p − 1 上,或者切换到“反求”找出所有满足 φ(n) = m 的 n。
常见问题
为什么 φ(1) = 1?
因为 gcd(1, 1) = 1:从 1 到 1 唯一的数与 1 互素。这个约定也让公式保持成立,例如高斯关于 n 的因数的求和公式,在 n = 1 时就是 φ(1) = 1。
φ 和素数计数函数是一回事吗?
不是。π(n) 统计不超过 n 的素数,φ(n) 统计不超过 n 且与 n 互素的数。φ(10) = 4 统计的是 1、3、7 和 9,而 π(10) = 4 统计的是 2、3、5 和 7。它们在这里相等只是巧合:φ(12) = 4,但 π(12) = 5。
φ(n) 能算多快?
能多快分解 n,就能多快算出 φ(n)。知道素因数后只需几次乘法;不知道的话,目前没有已知的快速方法,而 RSA 正依赖于这一点。对不超过 10^18 的数,浏览器中的分解只需几毫秒;对几百位的数,可能需要好几年。
哪些数的 φ(n) 相对于 n 最小?
有很多小素因数的数。φ(n)/n = (1 − 1/p₁)(1 − 1/p₂)… 只取决于哪些素数整除 n,与它们的幂次无关:对 2 的任何幂都恰好是 1/2,对 30 = 2 × 3 × 5 是 8/30,约 27%。前 15 个素数的乘积 614,889,782,588,491,410 的 φ(n)/n ≈ 14%,是不超过 10^18 的所有数中最低的。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
打开欧拉函数计算器