欧拉函数 φ(n)：定义、积性与公式

在 $1,2,\dots,n$ 里，有多少个数和 $n$ 互素？这个计数记作 $\varphi(n)$，叫欧拉函数。它看起来只是在数个数，真正要抓住的却是三件事：定义在数什么、为什么互素模数上可以拆开乘、以及公式 $\varphi(n)=n\prod_{p\mid n}(1-1/p)$ 从哪来。

定义：就是在数互素

正整数 $n$ 的欧拉函数是

也就是 $\{1,2,\dots,n\}$ 中与 $n$ 互素的个数。约定 $\varphi(1)=1$，因为 $\gcd(1,1)=1$。

例如 $n=10$：和 $10$ 互素的是 $1,3,7,9$，所以 $\varphi(10)=4$。$n=7$ 是素数，前面六个都和它互素，所以 。一般地，素数 满足 。

这个定义本身就是「与互素个数的关系」：$\varphi(n)$ 不是后补的抽象符号，它就是那个个数。后面的积性和公式，都是为了不用一个一个去试 $\gcd$。

区间取 $1$ 到 $n$ 还是 $0$ 到 $n-1$，答案一样。$0$ 与 $n$ 不互素（$n>1$ 时），而 本身也不与 互素，两边各少一个，计数不变。 时两边都只剩 这一个。所以写 也常见，尤其在谈剩余类的时候。

换一个群论的说法，意思完全一样。模 $n$ 的剩余类里，有乘法逆元的恰好是那些与 $n$ 互素的类：裴蜀定理保证 $\gcd(a,n)=1$ 当且仅当存在 $x$ 使 $ax\equiv 1\pmod n$。这些可逆类组成乘法群 ，阶就是 。所以「互素个数」和「可逆剩余类个数」是同一件事。

还可以问一个略宽的问题：在 $1$ 到 $n$ 里，与 $n$ 的最大公因数恰好是 $d$ 的有多少个？令 $a=d b$，条件变成 $\gcd(b,n/d)=1$ 且 ，于是恰好 个。特别地 就回到 。这个分组后面证明 时还要用。

几个立刻能算的特例

• $\varphi(1)=1$
• $p$ 为素数：$\varphi(p)=p-1$
• $p^k$ 为素幂：在 到 里，不互素的恰好是 的倍数，有 个，所以

$n=9=3^2$：不互素的是 $3,6,9$，剩下 $1,2,4,5,7,8$，共 个，对上 。

$n=8=2^3$：和 $8$ 互素的只能是奇数 $1,3,5,7$，共 $4$ 个，对上 $8(1$。

素幂之所以好算，是因为「不互素」只有一种原因：被唯一的那个 $p$ 整除。合数一旦有两个不同素因子，不互素的方式就交叉了，必须用积性或容斥把交叉减干净。

积性：互素就可以拆

数论里说一个函数 $f$ 是积性的，意思是：只要 $\gcd(m,n)=1$，就有

若对任意 $m,n$（不要求互素）都成立，叫完全积性。$\varphi$ 是积性的，但不是完全积性：$\varphi(4)=2$，而 $\varphi(2)\varphi(2)=1$，对不上。

为什么互素时能拆？中国剩余定理给一个双射。$\gcd(m,n)=1$ 时，映射

是一一对应。左边与 $mn$ 互素，当且仅当右边分别与 $m$、$n$ 互素：因为素数 $p$ 若整除 $mn$ 又整除 $a$，则 $p$ 整除 $m$ 或 ，于是对应分量也不互素。反过来也对。于是互素剩余类的个数相乘：

不必把 CRT 的构造全写一遍。只要接受「模 $mn$ 的一个数，同时被模 $m$ 和模 $n$ 的一对余数唯一确定」，互素条件就会按分量拆开。

用 $m=3$、$n=4$ 看一眼。模 $12$ 与 $12$ 互素的是 $1,5,7,11$，共 $4$ 个。模 互素的有 个，模 互素的有 个，。配对是

右边恰好穷尽「模 $3$ 互素」$\times$「模 $4$ 互素」的四对。

若不用 CRT 的语言，也可以直接数。设 $\gcd(m,n)=1$。在 $1$ 到 $mn$ 里取 $a$，把它写成 $a=qn+r$，其中 。要 ，必须同时 和 。前者只依赖于 ，所以 必须落在与 互素的 种余数上。对固定的这种 ，再看 时 模 的变化：因为 模 可逆，这 个数恰好跑遍所有模 剩余类，其中与 互素的有 个。于是总数是 。

这条计数和 CRT 是同一件事，只是把双射拆成「先定模 $n$ 的余数，再数模 $m$ 还剩多少选择」。

公式从素因子分解来

任意 $n>1$ 写成

各素因子幂两两互素，反复用积性：

这就是标准公式。乘积只跑过互异的素因子，指数 $k_i$ 已经收进前面的 $n$ 里。写成

同一回事，手算时往往更好用：先把 $n$ 对每个素因子各约掉一份，再乘上 $p-1$。等价地：

$n=p^k$ 时公式退化成上一节的素幂情形，所以局部和全局是对齐的。

公式里真正依赖的是 $n$ 的素因子集合，不是指数。因此 $\varphi(12)=\varphi(4\cdot 3)$ 和 $\varphi(6\cdot 2)$ 的拆法不同，但 $\varphi(p^k)/p^k=1-1/p$ 对所有 都一样：。比值 等于 ，只看 被哪些素数除得尽。

这也解释了为什么分解时不必记住每个指数对公式「多贡献了什么」：指数已经在前面的 $n$ 里，乘积部分每个 $p$ 只出现一次。手算最稳的顺序是：写出标准分解，抄下互异素数，再从 $n$ 出发依次乘 $(p-1)/p$。

另一种证明：容斥

不一定走积性。在 $1$ 到 $n$ 里先假定全都算上，有 $n$ 个。再丢掉被某个素因子 $p$ 整除的，每个 $p$ 挖掉 $n/p$ 个。两个素因子 $p,q$ 同时整除的被减了两次，要加回 。这就是容斥：

和前面同一条公式。积性证明解释「为什么能拆成局部」，容斥证明解释「为什么每个素因子贡献一个 $1-1/p$」。

把 $n=30=2\cdot 3\cdot 5$ 展开一次就清楚了。$1$ 到 $30$ 共 $30$ 个数。被 $2$ 整除的 $15$ 个，被 整除的 个，被 整除的 个；两两相交： 有 个， 有 个， 有 个；三个都整除的只有 自己， 个。于是

公式给出 $30\cdot 1/2\cdot 2/3\cdot 4/5=8$。列出互素的：$1,7,11,13,17,19,23,29$。容斥每一步都对应「至少被这些素因子整除」，最后剩下的就是一个素因子都不沾的那些。

还有一个常用恒等式，证明公式时也常碰到：

原因是把 $\{1,2,\dots,n\}$ 按 $\gcd(a,n)=d$ 分组。每组里 $a=d\cdot b$，且 ，所以该组恰好有 个元素。令 ，得到右边是所有 的和，等于 。

例如 $n=12$ 的因数是 $1,2,3,4,6,12$，

这个式子可以用莫比乌斯反演推回 $\varphi(n)=\sum_{d\mid n}\mu(d)\,n/d$，再展开 $\mu$，又得到同一条乘积公式。三条路走到同一处，说明公式不是凑出来的。

恒等式也可以当验算：算出一串 $\varphi(d)$ 之后，对某个 $n$ 把所有因数上的值加起来，应当恰好等于 $n$。手算 $\varphi(36)=12$ 之后，可以再加 $\phi (1)+\phi (2)+\phi (3)+\phi (4)+\phi (6)+\phi (9)+\phi (12)$，应当得到 。加错了多半是某个素幂或积性用错了。

手算例子

例一：先分解再套公式

算 $\varphi(36)$。$36=2^2\cdot 3^2$，

或 $\varphi(36)=\varphi(4)\varphi(9)=2\cdot 6=12$。列出 $1$ 到 $36$ 中与 $36$ 互素的：，正好 个。

例二：素幂

$\varphi(32)=\varphi(2^5)=2^4=16$。和 $32$ 互素就是奇数，$1$ 到 有 个奇数。

例三：三个不同素数

$\varphi(105)$。$105=3\cdot 5\cdot 7$，

逐步算：$105\times 2/3=70$，$70\times 4/5=56$，$56\times 6/7=48$。也可以先写成 $$。中间带着 连乘时，每一步都整除，不容易乘错。

例四：不是完全积性

比较 $\varphi(12)$ 和 $\varphi(2)\varphi(6)$。$12=2^2\cdot 3$，$\phi (12)=12\cdot 1\mathrm{/}2\cdot 2\mathrm{/}3$。，，乘积是 ，对不上。因为 和 不互素，积性用不上。

若硬拆 $12=3\cdot 4$，两边互素，就恢复 $\varphi(3)\varphi(4)=2\cdot 2=4$。

例五：用定义核对一个合数

$n=15=3\cdot 5$。按公式 $\varphi(15)=15\cdot 2/3\cdot 4/5=8$。按定义，$1$ 到 里与 互素的是 ，共 个。被 或 整除的都被排除了，正好是容斥在小数上的样子。

例六：较大但仍可手算

$\varphi(360)$。$360=2^3\cdot 3^2\cdot 5$，

逐步：$360/2=180$，$180\cdot 2/3=120$，$120\cdot 4/5=96$。用另一写法：$\phi (8)\phi (9)\phi (5)=4$。两种路径对得上，通常说明分解没有漏素因子。

若题目给的是「$1$ 到 $360$ 中与 $360$ 互素的数有多少」，不要去枚举，直接算 $\varphi(360)$。这就是定义与公式的分工：定义告诉你在数什么，公式告诉你怎么数。

一份可直接用的实现

计算 $\varphi(n)$ 的关键是试除分解。试到 $\sqrt{n}$ 即可；每碰到一个素因子 $p$，先把 $n$ 里的 $$ 除尽，同时用 贡献因子 。

跑一下，两列应完全一致，并和前面的手算对上：$1,6,4,6,4,4,8,16,12,48$。euler_phi 是 $O(\sqrt n)$，单次查询足够。需要很多 时，改成线性筛，让每个素数走过自己的倍数，按公式乘上一次 。

筛法的意思是：每个素数 $p$ 走过它的倍数 $j$，给 $j$ 乘上一次 $(1-1/p)$。每个合数只会被自己的各个互异素因子各改一次，正好对应公式里的乘积。时间 $O(N\log\log N)$，和埃氏筛同级。

若只要前 $N$ 项，筛比反复试除快一个数量级以上；若只要单个很大的 $n$，试除仍然更合适。

线性筛还可以在分解的同时递推。记最小素因子 $\mathrm{lpf}(n)=p$，写出 $n=p^k m$ 且 $p\nmid m$，则

实现时常见两种转移：若 $p^2\mid n$，则 $\varphi(n)=\varphi(n/p)\cdot p$；否则 $\varphi(n)=\varphi(n/p)\cdot(p-1)$。前者对应多乘一个已经出现过的素因子，比值 不变，所以 只按 放大；后者是第一次碰到 ，要补上 。和单点试除是同一套公式，只是把分解摊到筛的过程里。

写代码时容易踩的坑

$n=1$ 要单独成立。循环从 $2$ 开始试除时，$x$ 一开始就是 $1$，不会进任何素因子分支，result 保持 $1$，这是对的。不要特判成 $0$。

更新用 result -= result // p，不要写成先乘 $p-1$ 再除 $p$ 却把顺序弄反。整数除法必须整除；先减再除能保证每一步都是整数，因为此时 $p$ 整除当前的 result。

只对每个互异素因子更新一次。内层 while 把 $p$ 除尽，外层才做减法。如果每个 $p$ 的幂次都减一次，就会把 $\varphi(p^k)$ 算成 $p^k(1-1/p)^k$。

试除上界是变化中的 $x$，不是原始的 $n$。把小因子剥掉之后 $x$ 变小，循环可以更早停。最后若 $x>1$，它本身是一个大于 $\sqrt{n_{\text{原}}}$ 的素因子，还要再贡献一次。

$\varphi(n)$ 对 $n\ge 3$ 一定是偶数。这可以当断言：算完若得到奇数且 $n>2$，多半是漏了一个素因子。原因是：奇数素因子贡献偶数 $p-1$；若 $n$ 是 $$ 的幂且至少是 ，则 也是偶数。

不要对不互素的因子用积性。euler_phi(m) * euler_phi(n) 只有在 $\gcd(m,n)=1$ 时才等于 $\varphi(mn)$。测例里放一组 $\varphi(12)$ 对 $\varphi(2)\varphi(6)$，能把这个错觉挡住。

$\varphi(n)$ 本身可以比 $n$ 小很多。$n$ 的小素因子越多，$\prod(1-1/p)$ 越小。例如 $\varphi(30)/30=8/30\approx 0.267$，而素数处 接近 。写随机测试时不要默认「答案大概是 的一半」；偶数已经至少打了 ，再乘几个小素数会继续往下掉。

和欧拉定理的边界

欧拉定理说：若 $\gcd(a,n)=1$，则

所以 $\varphi(n)$ 也是群 $(\mathbb{Z}/n\mathbb{Z})^\times$ 的阶。模逆、RSA 的指数、把费马小定理从素数模扩到一般模，都会用到它。费马小定理是特例：$n=p$ 素数时 $\varphi(p)=p-1$，于是 。

这些是 $\varphi$ 的去处，不是定义本身。先把「数互素个数」和乘积公式算准，再用到定理不迟。定理要成立，前提恰好是 $a$ 落在那 $\varphi(n)$ 个互素类里；不互素时连逆元都没有，幂次同余要另说。

收束

$\varphi(n)$ 的定义就是 $1$ 到 $n$ 里与 $n$ 互素的个数。互素模数上它按 CRT 拆开，因而是积性的；落到素因子上，每个 $p$ 贡献 $1-1/p$，于是

手算先分解，再连乘；代码里试除或线性筛做同一件事。不必把它看成一串要背的式子。把计数、积性和容斥对上，公式就会自己长出来。

回到开头那句问话：$\varphi(n)$ 就是 $1$ 到 $n$ 里与 $n$ 互素的个数。会算这个数，一次同余里「有几个可逆元」、RSA 里「模 $n$ 的乘法群有多大」，才有地方落脚。公式是加速计数的工具，不是另一套定义。