不超过 36 且与它没有公因数的整数有 12 个。连乘的配方是拿 36 依次扔掉每个素因子的那些分数:乘 (1 − 1/2) 扔掉偶数,乘 (1 − 1/3) 扔掉 3 的倍数,工作台印 12。因为 36 = 2²·3²,可能共享的素数只有这两个。
第二个链接反过来数同一件事,用容斥:2 的倍数十八个,3 的倍数十二个,6 的倍数六个被减了两次所以要加回来——36 − 18 − 12 + 6 = 12。两条配方必须一致,一致的原因是「能被 2 或 3 整除」恰好就是「与 36 不互质」。φ 正是 RSA 运算赖以进行的那个数:欧拉定理说对一切与 n 互质的 a 都有 a^φ(n) ≡ 1 (mod n),所以这个数目有多大,循环就有多大。
答案
12
口径说明
工作台上的 36·(1 − 1/2)(1 − 1/3)。第二个链接是容斥算法,第三个是说清哪些素数起作用的标准分解 2²·3²。
出处
Euler's totient φ(36) = 36(1 − 1/2)(1 − 1/3) = 12, from his 1763 memoir on the function; the product form φ(n) = n·∏(1 − 1/p) over the primes dividing n is the standard result behind RSA key arithmetic
在计算器里做这道题
下面的链接直接打开对应的计算器,并把这道题的数字填进屏幕——答案就是上面那一行,可以自己核对。