オイラーの定理とは？数論の基礎から証明・応用まで完全解説！
オイラーの定理とは？数論の基礎から証明・応用まで完全解説！
目次
オイラーの定理とは？
オイラーの定理（Euler’s theorem）は、数論における重要な定理のひとつで、次のように表されます。
任意の整数 \\(a\\) と正の整数 \\(n\\) が互いに素（つまり \\(\gcd(a, n) = 1\\)）であるとき、
\\[ a^{\varphi(n)} \equiv 1 \pmod{n} \\]
が成り立ちます。ここで、\\(\varphi(n)\\) は「オイラーのトーシェント関数」と呼ばれる関数で、\\(n\\) 以下の整数のうち \\(n\\) と互いに素なものの個数を表します。
オイラーのトーシェント関数 \\(\varphi(n)\\) とは？
オイラーの定理の中心的役割を担うのがトーシェント関数（Euler’s totient function）です。\\(\varphi(n)\\) は、次のように定義されます。
- \\(\varphi(p) = p – 1\\) （\\(p\\) が素数）
- \\(\varphi(p^k) = p^k – p^{k-1}\\)
- \\(\varphi(mn) = \varphi(m)\varphi(n)\\) （\\(m\\) と \\(n\\) が互いに素）
例えば:
- \\(\varphi(5) = 4\\)（1, 2, 3, 4 が 5 と互いに素）
- \\(\varphi(6) = \varphi(2)\varphi(3) = 1 \times 2 = 2\\)
- \\(\varphi(10) = \varphi(2) \times \varphi(5) = 1 \times 4 = 4\\)
フェルマーの小定理との関係
オイラーの定理は、フェルマーの小定理の一般化とみなすことができます。
フェルマーの小定理は、\\(p\\) を素数、\\(a\\) を \\(p\\) と互いに素な整数とすると、
\\[ a^{p-1} \equiv 1 \pmod{p} \\]
が成り立つ、という定理です。素数 \\(p\\) のとき、\\(\varphi(p) = p – 1\\) なので、オイラーの定理に一致します。
オイラーの定理の証明
オイラーの定理は以下のように証明されます。
- \\(n\\) と互いに素な整数の集合を \\(R = \{r_1, r_2, \ldots, r_{\varphi(n)}\}\\) とします。
- この集合の各要素に \\(a\\) を掛けた集合 \\(S = \{ar_1, ar_2, \ldots, ar_{\varphi(n)}\}\\) を考えます。
- 各 \\(ar_i\\) も \\(n\\) と互いに素であり、\\(R\\) と \\(S\\) は合同式のもとで同じ集合（順序は異なる）になります。
- よって、積の合同式が成り立ちます: \\[ ar_1 \cdot ar_2 \cdots ar_{\varphi(n)} \equiv r_1 r_2 \cdots r_{\varphi(n)} \pmod{n} \\]
- 左辺を整理すると: \\[ a^{\varphi(n)} \cdot r_1 r_2 \cdots r_{\varphi(n)} \equiv r_1 r_2 \cdots r_{\varphi(n)} \pmod{n} \\]
- 両辺から \\(r_1 r_2 \cdots r_{\varphi(n)}\\) を消去（これは \\(n\\) と互いに素なので可）して、 \\[ a^{\varphi(n)} \equiv 1 \pmod{n} \\] が導かれます。
具体例で理解しよう
例1: \\(a = 3, n = 10\\)
- \\(\gcd(3, 10) = 1\\) よって適用可能
- \\(\varphi(10) = \varphi(2)\varphi(5) = 1 \times 4 = 4\\)
- \\(3^4 = 81 \equiv 1 \pmod{10}\\)
例2: \\(a = 7, n = 15\\)
- \\(\gcd(7, 15) = 1\\)
- \\(\varphi(15) = \varphi(3) \times \varphi(5) = 2 \times 4 = 8\\)
- \\(7^8 = 5764801 \equiv 1 \pmod{15}\\)
応用例：RSA暗号との関係
RSA暗号では、公開鍵 \\(e\\) と秘密鍵 \\(d\\) を使って、次の関係を構築します。
\\[ e \cdot d \equiv 1 \pmod{\varphi(n)} \\]
ここで \\(n = pq\\)、\\(p\\) と \\(q\\) は大きな素数です。RSAの安全性は、\\(\varphi(n)\\) の計算が素因数分解を前提とする点にあります。
オイラーの定理を用いることで、暗号文 \\(c = m^e \mod n\\) に対し、
\\[ m = c^d \mod n \\]
と復号できることが保証されます。
このように、オイラーの定理は理論的にも実用的にも非常に重要な結果です。
