最後更新：2026-07-13

定義

歐拉函數 $\varphi(n)$ 計算 $1$ 到 $n$ 之間有多少整數與 $n$ 互質——也就是與 $n$ 除 $1$ 以外沒有公因數的整數。當兩個整數的最大公因數為 $1$ 時，稱它們互質。

例如 $\varphi(9) = 6$：在 $1, 2, \dots, 9$ 中，$1, 2, 4, 5, 7, 8$ 與 $9$ 互質，而 $3, 6, 9$ 則否。

此函數以萊昂哈德·歐拉命名，他於 1763 年提出。它也寫作 $\phi(n)$，並稱為 phi 函數。

乘積公式

其實不必檢驗每個不超過 $n$ 的整數。一旦把 $n$ 分解為相異質因數，函數值便可直接求得：

$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$

乘積對整除 $n$ 的相異質數取值——指數並不出現。每個質數 $p$ 去除 $1/p$ 比例的整數（即可被 $p$ 整除者），而由於各質數獨立作用，這些比例相乘。

範例——n = 36。 質因數分解為 $36 = 2^2 \cdot 3^2$，故相異質數為 $2$ 與 $3$：

$\varphi(36) = 36\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) = 36 \cdot \frac{1}{2} \cdot \frac{2}{3} = 12$

與 $36$ 互質的十二個整數為 $1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35$。

質數與質數冪

兩個基本情形讓公式易於理解：

• 質數 $p$： $1$ 到 $p - 1$ 的每個整數都與 $p$ 互質，因此 $\varphi(p) = p - 1$。例如 $\varphi(7) = 6$。
• 質數冪 $p^k$： 與 $p^k$ 不互質的整數只有 $p$ 的倍數，共 $p^{k-1}$ 個。於是

$\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)$

所以 $\varphi(8) = \varphi(2^3) = 2^2(2 - 1) = 4$，$\varphi(27) = \varphi(3^3) = 3^2(3 - 1) = 18$。

積性

歐拉函數是積性的：只要 $m$ 與 $n$ 互質，

$\varphi(mn) = \varphi(m)\,\varphi(n)$

這正是乘積公式成立的原因——把 $n$ 寫成質數冪之積，對每一項套用 $\varphi(p^k) = p^{k-1}(p-1)$ 再相乘即可。例如 $36 = 4 \cdot 9$ 且 $\gcd(4, 9) = 1$，故 $\varphi(36) = \varphi(4)\,\varphi(9) = 2 \cdot 6 = 12$。

須注意互質條件：當 $m$ 與 $n$ 有公因數時，$\varphi(mn) = \varphi(m)\varphi(n)$ 可能不成立。例如 $\varphi(2 \cdot 2) = \varphi(4) = 2$，而非 $\varphi(2)\varphi(2) = 1$。

歐拉定理

歐拉函數主導模冪運算。歐拉定理指出：若 $\gcd(a, n) = 1$，則

$a^{\varphi(n)} \equiv 1 \pmod{n}$

這是費馬小定理（質數 $p$ 時 $a^{p-1} \equiv 1 \pmod p$）的推廣，後者正是 $n = p$、$\varphi(p) = p - 1$ 的特例。

範例。 取 $a = 3$、$n = 10$。此時 $\varphi(10) = 4$，故 $3^4 = 81 \equiv 1 \pmod{10}$——的確 $81$ 的個位為 $1$。此定理可在計算前先把巨大指數對 $\varphi(n)$ 取模化簡。

在 RSA 的應用

RSA 公開金鑰密碼學直接建立於歐拉函數之上。模數由兩個大質數構成 $n = p \cdot q$，於是

$\varphi(n) = (p - 1)(q - 1)$

公開指數 $e$ 與私密指數 $d$ 的選取須滿足 $e \cdot d \equiv 1 \pmod{\varphi(n)}$。歐拉定理隨即保證解密可還原加密：$(m^e)^d \equiv m \pmod n$。

安全性來自一道落差：任何人都可公開 $n$，但要計算 $\varphi(n) = (p-1)(q-1)$ 卻須知道 $p$ 與 $q$。僅由 $n$ 還原兩者，就是分解一個大的半質數——對於足夠大的質數，一般相信在計算上不可行。事實上，知道 $\varphi(n)$ 等同於分解 $n$。

範例

$n$	分解	乘積形式	$\varphi(n)$
$10$	$2 \cdot 5$	$10\,(1 - \tfrac12)(1 - \tfrac15)$	$4$
$12$	$2^2 \cdot 3$	$12\,(1 - \tfrac12)(1 - \tfrac13)$	$4$
$36$	$2^2 \cdot 3^2$	$36\,(1 - \tfrac12)(1 - \tfrac13)$	$12$
$100$	$2^2 \cdot 5^2$	$100\,(1 - \tfrac12)(1 - \tfrac15)$	$40$
$101$	$101$（質數）	$101\,(1 - \tfrac{1}{101})$	$100$

特殊情形

• $n = 1$： 依慣例 $\varphi(1) = 1$。範圍內唯一的整數 $1$ 與自身互質。
• $n$ 為質數： $\varphi(n) = n - 1$，是此大小的最大值——質數擁有最多的互質剩餘。
• $n$ 為偶數： 因子 $(1 - \tfrac12)$ 至少去除一半整數，故 $\varphi(n) \le n/2$。
• 對因數求和： $n$ 所有因數的歐拉函數之和等於 $n$ 本身：$\sum_{d \mid n} \varphi(d) = n$。以 $n = 12$ 為例：$\varphi(1) + \varphi(2) + \varphi(3) + \varphi(4) + \varphi(6) + \varphi(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12$。

速查表

概念	公式
定義	$\varphi(n) = \#\{\, k : 1 \le k \le n,\ \gcd(k, n) = 1 \,\}$
乘積公式	$\varphi(n) = n \prod_{p \mid n} (1 - 1/p)$
質數	$\varphi(p) = p - 1$
質數冪	$\varphi(p^k) = p^{k-1}(p - 1)$
積性	當 $\gcd(m, n) = 1$ 時 $\varphi(mn) = \varphi(m)\varphi(n)$
歐拉定理	當 $\gcd(a, n) = 1$ 時 $a^{\varphi(n)} \equiv 1 \pmod n$
因數和	$\sum_{d \mid n} \varphi(d) = n$

常見問題（FAQ）

什麼是歐拉函數？

歐拉函數 φ(n) 計算不超過 n 且與 n 互質的正整數個數——也就是與 n 除 1 以外沒有公因數的整數。例如 φ(9) = 6，因為 1、2、4、5、7、8 都與 9 互質，而 3、6、9 則不然。依慣例 φ(1) = 1。

如何計算 φ(n)？

先把 n 分解為相異質數 p₁、p₂、…、pₖ，再套用 φ(n) = n · ∏(1 − 1/p) 對這些質數取乘積。以 n = 36 = 2² · 3² 為例，φ(36) = 36 · (1 − 1/2) · (1 − 1/3) = 36 · 1/2 · 2/3 = 12。只有相異質數才有影響，指數並不重要。

質數的歐拉函數是多少？

對質數 p，1 到 p − 1 的每個整數都與 p 互質，因此 φ(p) = p − 1。對質數冪 pᵏ，公式給出 φ(pᵏ) = pᵏ − pᵏ⁻¹ = pᵏ⁻¹(p − 1)。例如 φ(7) = 6，φ(8) = φ(2³) = 8 − 4 = 4。

為什麼歐拉函數在 RSA 與歐拉定理中很重要？

歐拉定理指出：若 gcd(a, n) = 1，則 a^φ(n) ≡ 1 (mod n)，這是費馬小定理的推廣。RSA 加密正建立於此：對兩個質數乘積 n = p·q，有 φ(n) = (p − 1)(q − 1)，而公鑰與私鑰指數的選取須滿足 e·d ≡ 1 (mod φ(n))。知道 φ(n) 等同於分解 n，這正是 RSA 安全性的來源。