欧拉函数

定义

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

比如说。

当是质数的时候，显然有。

性质

欧拉函数是积性函数。

即对任意满足的整数，有。

特别地，当是奇数时。

证明参见剩余系的复合。
。

证明

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

也可以这样考虑：如果，那么。

如果我们设表示的数的个数，那么。

根据上面的证明，我们发现，，从而。注意到约数和具有对称性，所以上式化为。
若，其中是质数，那么。（根据定义可知）
由唯一分解定理，设，其中是质数，有。
证明
- 引理：设为任意质数，那么。
  
  证明：显然对于从 1 到的所有数中，除了个的倍数以外其它数都与互素，故，证毕。
  
  接下来我们证明。由唯一分解定理与函数的积性
对任意不全为的整数，。

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

实现

如果只要求一个数的欧拉函数值，那么直接根据定义质因数分解的同时求就好了。这个过程可以用 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

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

详见：筛法求欧拉函数

应用

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

在结论

中代入，则有

其中，称为 Iverson 括号，只有当命题为真时取值为，否则取。对上式求和，就可以得到

这里关键的观察是，即在和之间能够被整除的的个数是。

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

GCD SUM

给定，求

思路

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

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

欧拉定理

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

若，则。

扩展欧拉定理

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

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

参考资料与注释

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

最后更新: 2024年9月29日
创建日期: 2018年7月11日