欧拉函数

定义

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

比如说 $\phi (1)=1$。

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

性质

• 欧拉函数是 积性函数。

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

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

  证明参见 剩余系的复合。

• $n={\sum }_{d\mid n}\phi (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)=\phi (\frac{n}{x})$，从而 $n={\sum }_{d\mid n}\phi (\frac{n}{d})$。注意到约数 $d$ 和 $\frac{n}{d}$ 具有对称性，所以上式化为 $n={\sum }_{d\mid n}\phi (d)$。

• 若 $n=p^k$，其中 $p$ 是质数，那么 $\phi (n)=p^k-p^{k-1}$。 （根据定义可知）

• 由唯一分解定理，设 $n={\prod }_{i=1}^s{p}_i^{k_i}$，其中 $p_i$ 是质数，有 $\phi (n)=n\times {\prod }_{i=1}^s\frac{p_i-1}{p_i}$。

证明

• 引理：设 $p$ 为任意质数，那么 $\phi (p^k)=p^{k-1}\times (p-1)$。

  证明：显然对于从 1 到 $p^k$ 的所有数中，除了 $p^{k-1}$ 个 $p$ 的倍数以外其它数都与 $p^k$ 互素，故 $\phi (p^k)=p^k-p^{k-1}=p^{k-1}\times (p-1)$，证毕。

接下来我们证明 $\phi (n)=n\times {\prod }_{i=1}^s\frac{p_i-1}{p_i}$。由唯一分解定理与 $\phi (x)$ 函数的积性

$$\begin{array}{rlr}\phi (n)& =\prod _{i=1}^s\phi (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{array}$$

• 对任意不全为 $0$ 的整数 $m,n$，$\phi (mn)\phi (\gcd (m,n))=\phi (m)\phi (n)\gcd (m,n)$。

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

实现

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

参考实现

[list2tab]

• C++

  #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;
  }

• Python

  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}\phi (d)$$

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

$$\gcd (a,b)=\sum _{d|\gcd (a,b)}\phi (d)=\sum _d[d|a][d|b]\phi (d),$$

其中 $[\cdot ]$ 为 Iverson 括号。对上式求和，就可以得到

$$\sum _{i=1}^n\gcd (i,n)=\sum _d\sum _{i=1}^n[d|i][d|n]\phi (d)=\sum _d\lfloor \frac{n}{d}\rfloor [d|n]\phi (d)=\sum _{d|n}\lfloor \frac{n}{d}\rfloor \phi (d).$$

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

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

GCD SUM

给定 $n\le 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{\lfloor \frac{n}{d}\rfloor }^2\phi (d).$$

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

欧拉定理

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

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

扩展欧拉定理

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

$$a^b\equiv \{\begin{array}{ll}{a}^{b\mathrm{mod}\phi (m)},& \gcd (a,m)=1\\ a^b,& \gcd (a,m)\ne 1,b<\phi (m)\\ a^{b\mathrm{mod}\phi (m)+\phi (m)},& \gcd (a,m)\ne 1,b\ge \phi (m)\end{array}(\mathrm{mod}m)$$

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

习题

• SPOJ ETF. Euler Totient Function
• UVa 10179. Irreducible Basic Fractions
• UVa 10299. Relatives
• UVa 11327. Enumerating Rational Numbers
• TIMUS 1673. Admission to Exam
• Luogu P1390 公约数的和
• Luogu P2155 [SDOI2008] 沙拉公主的困惑
• Luogu P2568 GCD

参考资料与注释

Footnotes

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