36 以下與它沒有公因數的數有 12 個

尤拉函數寫成對質數的連乘,同一行容斥也能給出這個 12。

算術與函數 · 難度: 經典結論 · 更新於 2026-11-10

不超過 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

在計算機裡做這道題

下面的連結直接開啟對應的計算機,並把這道題的數字填進屏幕——答案就是上面那一行,可以自己核對。

本站為獨立第三方工具站,與 Casio、Texas Instruments 及其代理商無隸屬、代理或授權關係。型號名與產品名為各權利人商標,僅用於識別機型。

手冊中的操作序列依據「本站線上計算機同源佈局資料 + 公開產品事實」獨立撰寫;規格與地區配置以實機與廠商最新資料為準。