不超過 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
在計算機裡做這道題
下面的連結直接開啟對應的計算機,並把這道題的數字填進屏幕——答案就是上面那一行,可以自己核對。