跳转至

歐拉函數

定義

歐拉函數（Euler's totient function），即 \(\varphi(n)\)，表示的是小於等於 \(n\) 和 \(n\) 互質的數的個數。

比如説 \(\varphi(1) = 1\)。

當 n 是質數的時候，顯然有 \(\varphi(n) = n - 1\)。

性質

  • 歐拉函數是積性函數。

    積性是什麼意思呢？如果有 \(\gcd(a, b) = 1\)，那麼 \(\varphi(a \times b) = \varphi(a) \times \varphi(b)\)。

    特別地，當 \(n\) 是奇數時 \(\varphi(2n) = \varphi(n)\)。

  • \(n = \sum_{d \mid n}{\varphi(d)}\)。

    證明

    利用 莫比烏斯反演 相關知識可以得出。

    也可以這樣考慮：如果 \(\gcd(k, n) = d\)，那麼 \(\gcd(\dfrac{k}{d},\dfrac{n}{d}) = 1, ( k < n )\)。

    如果我們設 \(f(x)\) 表示 \(\gcd(k, n) = x\) 的數的個數，那麼 \(n = \sum_{i = 1}^n{f(i)}\)。

    根據上面的證明，我們發現，\(f(x) = \varphi(\dfrac{n}{x})\)，從而 \(n = \sum_{d \mid n}\varphi(\dfrac{n}{d})\)。注意到約數 \(d\) 和 \(\dfrac{n}{d}\) 具有對稱性，所以上式化為 \(n = \sum_{d \mid n}\varphi(d)\)。

  • 若 \(n = p^k\)，其中 \(p\) 是質數，那麼 \(\varphi(n) = p^k - p^{k - 1}\)。 （根據定義可知）

  • 由唯一分解定理，設 \(n = \prod_{i=1}^{s}p_i^{k_i}\)，其中 \(p_i\) 是質數，有 \(\varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}}\)。

    證明

    • 引理：設 \(p\) 為任意質數，那麼 \(\varphi(p^k)=p^{k-1}\times(p-1)\)。

      證明：顯然對於從 1 到 \(p^k\) 的所有數中，除了 \(p^{k-1}\) 個 \(p\) 的倍數以外其它數都與 \(p^k\) 互素，故 \(\varphi(p^k)=p^k-p^{k-1}=p^{k-1}\times(p-1)\)，證畢。

      接下來我們證明 \(\varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}}\)。由唯一分解定理與 \(\varphi(x)\) 函數的積性

      \[ \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} \]

實現

如果只要求一個數的歐拉函數值，那麼直接根據定義質因數分解的同時求就好了。這個過程可以用 Pollard Rho 算法優化。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#include <cmath>

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
import math
def euler_phi(n):
    m = math.isqrt(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
12
#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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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

如果是多個數的歐拉函數值，可以利用後面會提到的線性篩法來求得。 詳見：篩法求歐拉函數

歐拉定理

與歐拉函數緊密相關的一個定理就是歐拉定理。其描述如下：

若 \(\gcd(a, m) = 1\)，則 \(a^{\varphi(m)} \equiv 1 \pmod{m}\)。

擴展歐拉定理

當然也有擴展歐拉定理

\[ a^b\equiv \begin{cases} a^{b\bmod\varphi(p)},\,&\gcd(a,\,p)=1\\ a^b,&\gcd(a,\,p)\ne1,\,b<\varphi(p)\\ a^{b\bmod\varphi(p)+\varphi(p)},&\gcd(a,\,p)\ne1,\,b\ge\varphi(p) \end{cases} \pmod p \]

證明和 習題 詳見 歐拉定理

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：iamtwz, Chrogeek, Enter-tainer, StudyingFather, aofall, CCXXXI, CoelacanthusHex, 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, TrisolarisHD, Xeonacid, yuhuoji
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用