欧拉函数

定义

欧拉函数（Euler's totient function），即 $φ (n)$ ，表示的是小于等于 $n$ 和 $n$ 互质的数的个数。

比如说 $φ (1) = 1$ 。

当 $n$ 是质数的时候，显然有 $φ (n) = n - 1$ 。

性质

欧拉函数是积性函数。

即对任意满足 $gcd (a, b) = 1$ 的整数 $a, b$ ，有 $φ (a b) = φ (a) φ (b)$ 。

特别地，当 $n$ 是奇数时 $φ (2 n) = φ (n)$ 。

证明参见剩余系的复合。
$n = \sum_{d ∣ n} φ (d)$ 。

证明

利用莫比乌斯反演相关知识可以得出。

也可以这样考虑：如果 $gcd (k, n) = d$ ，那么 $gcd (\frac{k}{d}, \frac{n}{d}) = 1, (k < n)$ 。

如果我们设 $f (x)$ 表示 $gcd (k, n) = x$ 的数的个数，那么 $n = \sum_{i = 1}^{n} f (i)$ 。

根据上面的证明，我们发现， $f (x) = φ (\frac{n}{x})$ ，从而 $n = \sum_{d ∣ n} φ (\frac{n}{d})$ 。注意到约数 $d$ 和 $\frac{n}{d}$ 具有对称性，所以上式化为 $n = \sum_{d ∣ n} φ (d)$ 。
若 $n = p^{k}$ ，其中 $p$ 是质数，那么 $φ (n) = p^{k} - p^{k - 1}$ 。（根据定义可知）
由唯一分解定理，设 $n = \prod_{i = 1}^{s} p_{i}^{k_{i}}$ ，其中 $p_{i}$ 是质数，有 $φ (n) = n \times \prod_{i = 1}^{s} \frac{p_{i} - 1}{p_{i}}$ 。
证明
- 引理：设 $p$ 为任意质数，那么 $φ (p^{k}) = p^{k - 1} \times (p - 1)$ 。
  
  证明：显然对于从 1 到 $p^{k}$ 的所有数中，除了 $p^{k - 1}$ 个 $p$ 的倍数以外其它数都与 $p^{k}$ 互素，故 $φ (p^{k}) = p^{k} - p^{k - 1} = p^{k - 1} \times (p - 1)$ ，证毕。
接下来我们证明 $φ (n) = n \times \prod_{i = 1}^{s} \frac{p_{i} - 1}{p_{i}}$ 。由唯一分解定理与 $φ (x)$ 函数的积性
$\begin{aligned} φ (n) & = \prod_{i = 1}^{s} φ (p_{i}^{k_{i}}) \\ = \prod_{i = 1}^{s} (p_{i} - 1) \times {p_{i}}^{k_{i} - 1} \\ = \prod_{i = 1}^{s} {p_{i}}^{k_{i}} \times (1 - \frac{1}{p_{i}}) \\ = n \prod_{i = 1}^{s} (1 - \frac{1}{p_{i}}) & ◻ \end{aligned}$ $\begin{aligned} \varphi(n) &= \prod_{i=1}^{s} \varphi(p_i^{k_i}) \\ &= \prod_{i=1}^{s} (p_i-1)\times {p_i}^{k_i-1}\\ &=\prod_{i=1}^{s} {p_i}^{k_i} \times(1 - \frac{1}{p_i})\\ &=n~ \prod_{i=1}^{s} (1- \frac{1}{p_i}) &\square \end{aligned}$
对任意不全为 $0$ 的整数 $m, n$ ， $φ (m n) φ (gcd (m, n)) = φ (m) φ (n) gcd (m, n)$ 。

可由上一条直接计算得出。

实现

如果只要求一个数的欧拉函数值，那么直接根据定义质因数分解的同时求就好了。这个过程可以用 Pollard Rho 算法优化。

参考实现

C++Python

#include <cmath>

int euler_phi(int n) {
  int ans = n;
  for (int i = 2; i * i <= 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;
}

import math


def euler_phi(n):
    ans = n
    for i in range(2, math.isqrt(n) + 1):
        if n % i == 0:
            ans = ans // i * (i - 1)
            while n % i == 0:
                n = n // i
    if n > 1:
        ans = ans // n * (n - 1)
    return ans

如果是多个数的欧拉函数值，可以利用后面会提到的线性筛法来求得。

详见：筛法求欧拉函数

应用

欧拉函数常常用于化简一列最大公约数的和。国内有些文章称它为 欧拉反演¹。

在结论

n = \sum_{d | n} φ (d)

中代入 $n = gcd (a, b)$ ，则有

gcd (a, b) = \sum_{d | gcd (a, b)} φ (d) = \sum_{d} [d | a] [d | b] φ (d),

其中， $[\cdot]$ 称为 Iverson 括号，只有当命题 $P$ 为真时 $[P]$ 取值为 $1$ ，否则取 $0$ 。对上式求和，就可以得到

\sum_{i = 1}^{n} gcd (i, n) = \sum_{d} \sum_{i = 1}^{n} [d | i] [d | n] φ (d) = \sum_{d} ⌊ \frac{n}{d} ⌋ [d | n] φ (d) = \sum_{d | n} ⌊ \frac{n}{d} ⌋ φ (d) .

这里关键的观察是 $\sum_{i = 1}^{n} [d | i] = ⌊ \frac{n}{d} ⌋$ ，即在 $1$ 和 $n$ 之间能够被 $d$ 整除的 $i$ 的个数是 $⌊ \frac{n}{d} ⌋$ 。

利用这个式子，就可以遍历约数求和了。需要多组查询的时候，可以预处理欧拉函数的前缀和，利用数论分块查询。

GCD SUM

给定 $n \leq 100000$ ，求

\sum_{i = 1}^{n} \sum_{j = 1}^{n} gcd (i, j) .

思路

仿照上文的推导，可以得出

\sum_{i = 1}^{n} \sum_{j = 1}^{n} gcd (i, j) = \sum_{d = 1}^{n} {⌊ \frac{n}{d} ⌋}^{2} φ (d) .

此时需要从 $1$ 遍历到 $n$ 求欧拉函数，用线性筛做就可以 $O (n)$ 得到答案。

欧拉定理

与欧拉函数紧密相关的一个定理就是欧拉定理。其描述如下：

若 $gcd (a, m) = 1$ ，则 $a^{φ (m)} \equiv 1 (\mod m)$ 。

扩展欧拉定理

当然也有扩展欧拉定理，用于处理一般的 $a$ 和 $m$ 的情形。

a^{b} \equiv {\begin{cases} a^{b mod φ (m)}, & gcd (a, m) = 1 \\ a^{b}, & gcd (a, m) \neq 1, b < φ (m) \\ a^{b mod φ (m) + φ (m)}, & gcd (a, m) \neq 1, b \geq φ (m) \end{cases} (\mod m)

证明和习题详见欧拉定理。

参考资料与注释

这一说法并未见于学术期刊或国外的论坛中，在使用该说法时应当注意。 ↩

本页面最近更新：2025/5/3 19:43:25，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：iamtwz, Chrogeek, StudyingFather, aofall, CCXXXI, CoelacanthusHex, Enter-tainer, frank-xjh, Great-designer, greyqz, guodong2005, henrytbtrue, Ir1d, kZime, lihaoyu1234, Marcythm, MegaOwIer, Menci, nalemy, orzAtalod, ouuan, Persdre, segment-tree, ShaoChenHeng, shuzhouliu, sshwy, Struggler-q, Tiphereth-A, Xeonacid, yuhuoji, c-forrest, mgt, Pinghigh, shawlleyw, TrisolarisHD, TrisolarisHD
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用