跳转至

# 欧拉函数

## 定义

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

比如说 𝜑(1) =1 φ(1)=1．

当 𝑛 n 是质数的时候，显然有 𝜑(𝑛) =𝑛 −1 φ(n)=n−1．

## 性质

- 欧拉函数是 积性函数．

  即对任意满足 g c d(𝑎,𝑏) =1 gcd(a,b)=1 的整数 𝑎,𝑏 a,b，有 𝜑(𝑎 𝑏) =𝜑(𝑎)𝜑(𝑏)φ(a b)=φ(a)φ(b)．

  特别地，当 𝑛 n 是奇数时 𝜑(2 𝑛) =𝜑(𝑛)φ(2 n)=φ(n)．

  证明参见 剩余系的复合．

- 𝑛 =∑𝑑∣𝑛 𝜑(𝑑)n=∑d∣n φ(d)．

  证明

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

  也可以这样考虑：如果 g c d(𝑘,𝑛) =𝑑 gcd(k,n)=d，那么 g c d(𝑘 𝑑,𝑛 𝑑) =1,(𝑘 <𝑛)gcd(k d,n d)=1,(k<n)．

  如果我们设 𝑓(𝑥)f(x) 表示 g c d(𝑘,𝑛) =𝑥 gcd(k,n)=x 的数的个数，那么 𝑛 =∑𝑛 𝑖=1 𝑓(𝑖)n=∑i=1 n f(i)．

  根据上面的证明，我们发现，𝑓(𝑥) =𝜑(𝑛 𝑥)f(x)=φ(n x)，从而 𝑛 =∑𝑑∣𝑛 𝜑(𝑛 𝑑)n=∑d∣n φ(n d)．注意到约数 𝑑 d 和 𝑛 𝑑 n d 具有对称性，所以上式化为 𝑛 =∑𝑑∣𝑛 𝜑(𝑑)n=∑d∣n φ(d)．

- 若 𝑛 =𝑝 𝑘 n=p k，其中 𝑝 p 是质数，那么 𝜑(𝑛) =𝑝 𝑘 −𝑝 𝑘−1 φ(n)=p k−p k−1． （根据定义可知）

- 由唯一分解定理，设 𝑛 =∏𝑠 𝑖=1 𝑝 𝑘 𝑖 𝑖 n=∏i=1 s p i k i，其中 𝑝 𝑖 p i 是质数，有 𝜑(𝑛) =𝑛 ×∏𝑠 𝑖=1 𝑝 𝑖−1 𝑝 𝑖 φ(n)=n×∏i=1 s p i−1 p i．

  证明

  - 引理：设 𝑝 p 为任意质数，那么 𝜑(𝑝 𝑘) =𝑝 𝑘−1 ×(𝑝 −1)φ(p k)=p k−1×(p−1)．

    证明：显然对于从 1 到 𝑝 𝑘 p k 的所有数中，除了 𝑝 𝑘−1 p k−1 个 𝑝 p 的倍数以外其它数都与 𝑝 𝑘 p k 互素，故 𝜑(𝑝 𝑘) =𝑝 𝑘 −𝑝 𝑘−1 =𝑝 𝑘−1 ×(𝑝 −1)φ(p k)=p k−p k−1=p k−1×(p−1)，证毕．

  接下来我们证明 𝜑(𝑛) =𝑛 ×∏𝑠 𝑖=1 𝑝 𝑖−1 𝑝 𝑖 φ(n)=n×∏i=1 s p i−1 p i．由唯一分解定理与 𝜑(𝑥)φ(x) 函数的积性

  𝜑(𝑛)=𝑠∏𝑖=1 𝜑(𝑝 𝑘 𝑖 𝑖)=𝑠∏𝑖=1(𝑝 𝑖−1)×𝑝 𝑖 𝑘 𝑖−1=𝑠∏𝑖=1 𝑝 𝑖 𝑘 𝑖×(1−1 𝑝 𝑖)=𝑛 𝑠∏𝑖=1(1−1 𝑝 𝑖)◻φ(n)=∏i=1 s φ(p i k i)=∏i=1 s(p i−1)×p i k i−1=∏i=1 s p i k i×(1−1 p i)=n ∏i=1 s(1−1 p i)◻

- 对任意不全为 0 0 的整数 𝑚,𝑛 m,n，𝜑(𝑚 𝑛)𝜑(g c d(𝑚,𝑛)) =𝜑(𝑚)𝜑(𝑛)g c d(𝑚,𝑛)φ(m n)φ(gcd(m,n))=φ(m)φ(n)gcd(m,n)．

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

## 实现

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

参考实现
C++Python

     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
    12
    13
    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

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

详见：筛法求欧拉函数

## 应用

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

在结论

𝑛=∑𝑑|𝑛 𝜑(𝑑)n=∑d|n φ(d)

中代入 𝑛 =g c d(𝑎,𝑏)n=gcd(a,b)，则有

g c d(𝑎,𝑏)=∑𝑑|g c d(𝑎,𝑏)𝜑(𝑑)=∑𝑑[𝑑|𝑎][𝑑|𝑏]𝜑(𝑑),gcd(a,b)=∑d|gcd(a,b)φ(d)=∑d[d|a][d|b]φ(d),

其中 [ ⋅][⋅] 为 Iverson 括号．对上式求和，就可以得到

𝑛∑𝑖=1 g c d(𝑖,𝑛)=∑𝑑 𝑛∑𝑖=1[𝑑|𝑖][𝑑|𝑛]𝜑(𝑑)=∑𝑑⌊𝑛 𝑑⌋[𝑑|𝑛]𝜑(𝑑)=∑𝑑|𝑛⌊𝑛 𝑑⌋𝜑(𝑑).∑i=1 n gcd(i,n)=∑d∑i=1 n[d|i][d|n]φ(d)=∑d⌊n d⌋[d|n]φ(d)=∑d|n⌊n d⌋φ(d).

这里关键的观察是 ∑𝑛 𝑖=1[𝑑|𝑖] =⌊𝑛 𝑑⌋∑i=1 n[d|i]=⌊n d⌋，即在 1 1 和 𝑛 n 之间能够被 𝑑 d 整除的 𝑖 i 的个数是 ⌊𝑛 𝑑⌋⌊n d⌋．

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

GCD SUM

给定 𝑛 ≤1 0 0 0 0 0 n≤100000，求

𝑛∑𝑖=1 𝑛∑𝑗=1 g c d(𝑖,𝑗).∑i=1 n∑j=1 n gcd(i,j).
思路

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

𝑛∑𝑖=1 𝑛∑𝑗=1 g c d(𝑖,𝑗)=𝑛∑𝑑=1⌊𝑛 𝑑⌋2 𝜑(𝑑).∑i=1 n∑j=1 n gcd(i,j)=∑d=1 n⌊n d⌋2 φ(d).

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

## 欧拉定理

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

若 g c d(𝑎,𝑚) =1 gcd(a,m)=1，则 𝑎 𝜑(𝑚) ≡1(m o d 𝑚)a φ(m)≡1(mod m)．

### 扩展欧拉定理

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

𝑎 𝑏≡⎧{ {⎨{ {⎩𝑎 𝑏 m o d 𝜑(𝑚),g c d(𝑎,𝑚)=1 𝑎 𝑏,g c d(𝑎,𝑚)≠1,𝑏<𝜑(𝑚)𝑎 𝑏 m o d 𝜑(𝑚)+𝜑(𝑚),g c d(𝑎,𝑚)≠1,𝑏≥𝜑(𝑚)(m o d 𝑚)a b≡{a b mod φ(m),gcd(a,m)=1 a b,gcd(a,m)≠1,b<φ(m)a b mod φ(m)+φ(m),gcd(a,m)≠1,b≥φ(m)(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

## 参考资料与注释

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

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