欧拉函数

定义

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

比如说 。

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

性质

  • 欧拉函数是积性函数。

    积性是什么意思呢？如果有 ，那么 。

    特别地，当 是奇数时 。

  • 。

    证明

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

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

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

    根据上面的证明，我们发现，，从而 。注意到约数 和 具有对称性，所以上式化为 。

  • 若 ，其中 是质数，那么 。 （根据定义可知）

  • 由唯一分解定理，设 ，其中 是质数，有 。

    证明

    • 引理：设 为任意质数，那么 。

      证明：显然对于从 1 到 的所有数中，除了 个 的倍数以外其它数都与 互素，故 ，证毕。

      接下来我们证明 。由唯一分解定理与 函数的积性

实现

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// C++ Version
int euler_phi(int n) {
  int m = int(sqrt(n + 0.5));
  int ans = n;
  for (int i = 2; i <= m; 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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
# Python Version
def euler_phi(n):
    m = int(sqrt(n + 0.5))
    ans = n
    for i in range(2, m + 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

注：如果将上面的程序改成如下形式，会提升一点效率：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
// C++ Version
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
# Python Version
def euler_phi(n):
    ans = n
    for i in range(2, int(sqrt(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

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

欧拉定理

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

若 ，则 。

扩展欧拉定理

当然也有扩展欧拉定理

证明和 习题 详见 欧拉定理

build本页面最近更新：2022/9/19 14:41:33，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：iamtwz, Chrogeek, Enter-tainer, StudyingFather, CCXXXI, frank-xjh, Great-designer, greyqz, guodong2005, henrytbtrue, Ir1d, kZime, lihaoyu1234, MegaOwIer, nalemy, orzAtalod, ouuan, segment-tree, ShaoChenHeng, shuzhouliu, sshwy, Struggler-q, TrisolarisHD, Xeonacid
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论