最終更新: 2026-07-13

定義

オイラーのφ関数 $\varphi(n)$ は、$1$ から $n$ までの整数のうち $n$ と互いに素なもの、すなわち $n$ と $1$ 以外に公約数を持たないものの個数を数えます。2 つの整数が互いに素であるとは、その最大公約数が $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$ は $p$ の倍数、すなわち全体の $1/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$ と互いに素な 12 個の整数は $1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35$ です。

素数と素数のべき

公式を理解しやすくする基本的な 2 つの場合があります。

• 素数 $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 公開鍵暗号はトーシェントの上に直接構築されています。法は 2 つの大きな素数から $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 と互いに素なもの（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暗号はこれに基づきます。2つの素数の積 n = p·q に対して φ(n) = (p − 1)(q − 1) であり、公開鍵と秘密鍵の指数は e·d ≡ 1 (mod φ(n)) を満たすように選ばれます。φ(n) を知ることは n を素因数分解することと同等で、これが RSA の安全性を支えています。