Euler's Eyes
2026-10-10
数学の歴史
11 / 191 ページ
オイラーの定理と暗号
1763 では、オイラーは関数 $\varphi(n)$ (記号 $\varphi$ はガウスによって後から登場しました)、つまり $n$ と共通因数を持たない 1 から $n$ までの数の数を研究しました。 たとえば、$\varphi(10) = 4$ は、1 から 10 までは 1、3、7、9 のみが適しているためです。彼は、$a$ がそうではないことを証明しました。 $n$と共通因数があるので、
$$a^{\varphi(n)} \equiv 1 \pmod{n}.$$
$n = 10$ と $a = 3$ のアイデアを参照してください。数値 1、3、7、および 9 を 3 で乗算します。
$$3 \cdot 1 = 3, \quad 3 \cdot 3 = 9, \quad 3 \cdot 7 = 21 \equiv 1, \quad 3 \cdot 9 = 27 \equiv 7 \pmod{10}.$$
余りは3、9、1、7 の同じ 4 つの数字をシャッフルしただけです。したがって、彼らの製品は 同じ：
$$(3 \cdot 1)(3 \cdot 3)(3 \cdot 7)(3 \cdot 9) \equiv 1 \cdot 3 \cdot 7 \cdot 9 \pmod{10}$$
$$3^4 \cdot (1 \cdot 3 \cdot 7 \cdot 9) \equiv 1 \cdot 3 \cdot 7 \cdot 9 \pmod{10}.$$
$1 \cdot 3 \cdot 7 \cdot 9$ には 10 との共通因数がないため、両側でキャンセルできます。 $3^4 \equiv 1 \pmod{10}$。チェック: $3^4 = 81$。10 で割ると余りが 1 になります。同じ 引数は、$n$ との共通因数を持たない任意の $n$ および任意の $a$ に対して機能します。
$n$ が素数の場合、$\varphi(n) = n - 1$ となり、 定理はフェルマーの小定理となります。以上 200 年後の 1977 では、オイラーの定理は暗号化システムRSA の基礎となりました。 インターネットでの購入や携帯電話のメッセージを保護します。