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 及其代理商无隶属、代理或授权关系。型号名与产品名为各权利人商标,仅用于识别机型。

手册中的操作序列依据「本站在线计算器同源布局数据 + 公开产品事实」独立撰写;规格与地区配置以实机与厂商最新资料为准。