フェルマーの小定理

フェルマーの小定理

フェルマーの小定理は、数論の中で特に重要な素数に関する定理です。本定理は、整数と素数に関連する特性を明らかにし、実際にRSA暗号など多くの暗号技術にも応用されています。

概要

素数を表す記号として$p$、整数を表す記号として$a$を用います。このとき、次のような関係が成り立ちます。

1. $a^{p} \\equiv a \\ (mod \\ p)$
2. $a^{p-1} \\equiv 1 \\ (mod \\ p)$ （ここで$\gcd(a, p) = 1$という条件がある場合）

これらの関係式は、素数に対して特定の整数がどのように振る舞うかを示しています。特に、第二の式は「$a$が$p$の倍数でない場合、$a^{p-1}$は$p$で割った余りが1になる」と述べています。このように、フェルマーの小定理は数論の基本的な道具の一つとして広く認識されています。

定理の由来

この定理は17世紀初頭にフランスの数学者ピエール・ド・フェルマーによって発表されました。フェルマーが他の多くの予想と同様に、定理を確立したにもかかわらず、その証明は長い間発見されませんでした。彼の名前がついてはいますが、自らによる証明は存在しないと考えられています。実際の証明を聞いて初めて成立が示されたのは、後にゴットフリート・ライプニッツによるものでした。

証明方法

フェルマーの小定理にはいくつかの証明方法が存在しますが、以下に3つの主要な方法を紹介します。

証明方法1：数学的帰納法を用いた証明

1. 補題：$(m + 1)^{p} \\equiv m^{p} + 1 \\ (mod \\ p)$ という関係が成立することを示します。
2. 上記の補題を基にして、$a^{p} \\equiv a \\ (mod \\ p)$ を数学的帰納法によって証明します。具体的には、$m=0,1$ のときに成り立つことを確認した後、$m + 1$ に対しても同様のことを証明し、一般化します。

証明方法2：二項定理を使用する

1. 二項定理を適用した上で、$x^{p} + y^{p} \\equiv (x+y)^{p} \\ (mod \\ p)$ を示し、従って$ a^{p} \\equiv a \\ (mod \\ p)$を得ることができます。

証明方法3：集合論を利用する

1. $\{1, 2, ..., p-1\}$ と $\{a, 2a, ..., (p-1)a\}$ が同じものと見なせ、両者の要素を掛け合わせることで、$(p-1)! ≡ (p-1)! a^{p-1} \\ (mod \\ p)$ を導出します。ここから、$a^{p-1} \\equiv 1 \\ (mod \\ p)$ も成り立つことがわかります。

他の関連定理

この定理は後にレオンハルト・オイラーにより拡張され、オイラーの定理となりました。オイラーの定理では、整数$n$に互いに素な整数$a$に対しても同様の類似性が示されます。また、カーマイケルの定理などでも関連性が強調されています。

フェルマーテスト

フェルマーの小定理は、確率的素数判定法を用いるフェルマーテストに利用され、与えられた数が素数であるかどうかを高確率で判断するための手続きとしても使用されます。

参考文献

高木貞治『初等整数論講義』（第2版）
G.H. ハーディ、E・M・ライト『数論入門I』

このようにフェルマーの小定理は、数論という広大な科学領域において非常に重要な役割を果たしており、暗号技術など実用分野でもその価値が実証されています。

もう一度検索