互质与欧拉函数

本文部分参考李煜东《算法竞赛进阶指南》

更新记录：

• 2026/07/10：互质与欧拉函数部分基本完工

---

概述

定义

互质

$\forall a,b\in \mathbb{N}$，若 $\gcd (a,b)=1$，则称 $a,b$ 互质。

对于三个数或更多个数的情况，我们把 $\gcd (a,b,c)=1$ 的情况称为 $a,b,c$ 互质；把 $\gcd (a,b)=\gcd (a,c)=\gcd (b,c)=1$ 的情况称为 $a,b,c$ 两两互质。

欧拉函数

$1\sim N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记为 $\phi (N)$（读作 phi of n）。

---

一、欧拉函数的通项公式

若在算术基本定理中，$N=p_1^{c_1}{p}_2^{c_2}\cdots p_m^{c_m}$，则：

$$\phi (N)=N\cdot \frac{p_1-1}{p_1}\cdot \frac{p_2-1}{p_2}\cdots \frac{p_m-1}{p_m}=N\cdot \prod _{\text{质数 }p\mid N}\left(1-\frac{1}{p}\right)$$

证明

设 $p$ 是 $N$ 的质因子，$1\sim N$ 中 $p$ 的倍数有 $p,2p,3p,\dots ,(N/p)\cdot p$，共 $N/p$ 个。

同理，若 $q$ 也是 $N$ 的质因子，则 $1\sim N$ 中 $q$ 的倍数有 $N/q$ 个。如果我们将这 $N/p+N/q$ 个数去掉，那么 $p\cdot q$ 的倍数被排除了两次，需要加回来一次。因此，$1\sim N$ 中不与 $N$ 含有共同质因子 $p$ 或 $q$ 的数的个数为：

$$N-\frac{N}{p}-\frac{N}{q}+\frac{N}{pq}=N\cdot \left(1-\frac{1}{p}-\frac{1}{q}+\frac{1}{pq}\right)=N\cdot \left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right)$$

对 $N$ 的所有质因子依次应用上述容斥原理，即可得到欧拉函数的通项公式。

证毕。

实现

根据欧拉函数的通项公式，我们在用线性筛求质数时，可以顺便求出 $1\sim N$ 中每个数的欧拉函数值。

代码实现

int phi(int n) {
    int ans = n;
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0) {
            ans = ans / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}

---

二、欧拉函数的性质

性质一：$\phi (1)=1$

证明

$\gcd (1,1)=1$，所以 $[1,1]$ 中有 $1$ 个数与 $1$ 互质。

性质二：若 $p$ 为质数，则 $\phi (p)=p-1$

证明

若 $p$ 为质数，则 $1\sim p-1$ 中的所有数都与 $p$ 互质。

性质三：若 $n=p^k$（$p$ 为质数，$k>0$），则 $\phi (n)=p^k-p^{k-1}$

证明

在 $1\sim p^k$ 中，与 $n$ 不互质的数恰好是那些含有质因子 $p$ 的数，即 $p$ 的倍数：$p,2p,3p,\dots ,p\cdot p^{k-1}$，共 $p^{k-1}$ 个。因此与 $n$ 互质的数的个数为 $p^k-p^{k-1}$。

证毕。

性质四：$\forall n>1$，$1\sim n$ 中与 $n$ 互质的所有数之和为 $\frac{n\cdot \phi (n)}{2}$

证明

因为 $\gcd (n,x)=\gcd (n,n-x)$，所以与 $n$ 互质的数 $x$ 与 $n-x$ 成对出现，每一对的平均值为 $n/2$。因此所有与 $n$ 互质的数的平均值也为 $n/2$，总和即为 $\frac{n\cdot \phi (n)}{2}$。

证毕。

性质五：欧拉函数是积性函数

若 $\gcd (a,b)=1$，则 $\phi (ab)=\phi (a)\phi (b)$。

证明

对 $a$ 和 $b$ 分别分解质因数，由于 $a$ 与 $b$ 互质，它们的质因子集合无交集。根据欧拉函数的通项公式直接展开，即可得到 $\phi (ab)=\phi (a)\phi (b)$。

证毕。

特别地，当 $n$ 为奇数时，$\gcd (n,2)=1$，因此 $\phi (2n)=\phi (2)\cdot \phi (n)=\phi (n)$。

性质六：积性函数的质因数分解展开

若 $f$ 是积性函数，且在算术基本定理中 $n={\prod }_{i=1}^m{p}_i^{c_i}$，则 $f(n)={\prod }_{i=1}^{m}f(p_i^{c_i})$。

证明

将 $n$ 分解为互质的质数幂因子 $p_1^{c_1},p_2^{c_2},\dots ,p_m^{c_m}$，它们两两互质。根据积性函数的定义反复应用 $f(ab)=f(a)f(b)$（$\gcd (a,b)=1$），即可得到上式。

证毕。

性质七：设 $p$ 为质数，若 $p\mid n$ 且 $p^2\mid n$，则 $\phi (n)=\phi (n/p)\cdot p$

证明

若 $p\mid n$ 且 $p^2\mid n$，则 $n$ 与 $n/p$ 包含相同的质因子集合，只是 $p$ 的指数相差 $1$。将 $\phi (n)$ 与 $\phi (n/p)$ 分别按通项公式写出，二者相除，商为 $p$。

证毕。

性质八：设 $p$ 为质数，若 $p\mid n$ 但 $p^2\nmid n$，则 $\phi (n)=\phi (n/p)\cdot (p-1)$

证明

若 $p\mid n$ 但 $p^2\nmid n$，则 $n/p$ 与 $p$ 互质。由欧拉函数是积性函数（性质五）可得：

$$\phi (n)=\phi (p\cdot (n/p))=\phi (p)\cdot \phi (n/p)=(p-1)\cdot \phi (n/p)$$

证毕。

性质九：$\sum _{d\mid n}\phi (d)=n$

证明

设 $f(n)={\sum }_{d\mid n}\phi (d)$。若 $n,m$ 互质，则 $n$ 的约数与 $m$ 的约数两两相乘可得到 $nm$ 的所有约数，由乘法分配律可得：

$$f(nm)=\sum _{d\mid nm}\phi (d)=\left(\sum _{d\mid n}\phi (d)\right)\cdot \left(\sum _{d\mid m}\phi (d)\right)=f(n)\cdot f(m)$$

即 $f(n)$ 也是积性函数。

对于单个质因子 $p^m$，有：

$$f(p^m)=\sum _{d\mid p^m}\phi (d)=\phi (1)+\phi (p)+\phi (p^2)+\cdots +\phi (p^m)$$

由性质三，$\phi (p^k)=p^k-p^{k-1}$（$k\ge 1$），这是一个等比数列求和，结果为 $p^m$。

因此：

$$f(n)=\prod _{i=1}^{m}f(p_i^{c_i})=\prod _{i=1}^m{p}_i^{c_i}=n$$

证毕。

---

四、总结

由前面提到的性质 4 和性质 5：

1. 若 $p\mid n$ 且 $p^2\mid n$，则 $\phi (n)=\phi (n/p)\cdot p$；
2. 若 $p\mid n$ 但 $p^2\nmid n$，则 $\phi (n)=\phi (n/p)\cdot (p-1)$。
   在线性筛法中，每个合数 $n$ 只会被它的最小质因子 $p$ 筛一次。我们恰好可以在此执行上面两条判断，从 $\phi (n/p)$ 递推到 $\phi (n)$。

代码实现

int v[MAX_N], prime[MAX_N], phi[MAX_N];
void euler(int n) {
    memset(v, 0, sizeof(v)); // 最小质因子
    m = 0; // 质数数量
    for (int i = 2; i <= n; i++) {
        if (v[i] == 0) { // i 是质数
            v[i] = i, prime[++m] = i;
            phi[i] = i - 1;
        }
        // 给当前的数 i 乘上一个质因子
        for (int j = 1; j <= m; j++) {
            // i 有比 prime[j] 更小的质因子，或者超出 n 的范围，停止循环
            if (prime[j] > v[i] || prime[j] > n / i) break;
            // prime[j] 是合数 i*prime[j] 的最小质因子
            v[i*prime[j]] = prime[j];
            phi[i*prime[j]] = 
                phi[i] * (i % prime[j] ? prime[j] - 1 : prime[j]);
        }
    }
}

三、习题

仪仗队