フェルマーの小定理｜素数の合同式を表す基本定理

概要

フェルマーの小定理は、数論における基本的でありながら強力な結果で、17世紀にピエール・ド・フェルマーによって見いだされました。これは、整数を素数で割った余りを考えるとき、整数のべきに関して成り立つ単純な合同式を述べるものです。この定理は、素数に関する初等的な結果の多くを支えており、コンピュータのアルゴリズムで使われる実用的な判定法にもなっています。

定式化

最もよく知られた形は、任意の整数 a と任意の素数 p に対して、

a^p ≡ a (mod p)

です。

よく使われる系として、a が p で割り切れない場合（すなわち gcd(a,p)=1）の

a^(p−1) ≡ 1 (mod p)

があります。

これらは同値な表し方として、結果を導入するときに並べて示されることが多いです。この定理はピエール・ド・フェルマーの名にちなみ、素数とべきに関して彼に帰せられるいくつかの命題の一つです。簡潔な参照項目としては定理の項目を、素数に関する背景としては素数関連の資料を参照できます。

証明の考え方と歴史

初等的な証明には、組合せ論的または群論的な議論が用いられます。1つの方法では、p を法とする 0 でない剰余類を考え、gcd(a,p)=1 のとき a を掛ける操作がそれらの剰余類を置き換えることを示し、そこから a^(p−1) ≡ 1 という系が導かれます。歴史的にはこの結果はフェルマーによって述べられ、その後、群論や環論といった、より明確で一般的な枠組みが与えられ、関連結果の中での位置づけが理解されるようになりました。

応用と例

フェルマーの小定理は、高速累乗アルゴリズム、合同算術の簡約、そして簡単な素数判定法の基礎として使われます。例として、p=7、a=2 のとき、2^7 ≡ 2 (mod 7) であるため、2^6 ≡ 1 (mod 7) が成り立ちます。実際には、この定理により、素数を法とする大きな指数の計算を簡単に扱えます。

限界と関連結果

この定理の逆は成り立ちません。多くの a について a^(n−1) ≡ 1 (mod n) を満たす整数 n が、必ずしも素数とは限らないからです。このようなふるまいを示す合成数にはカーマイケル数があります。古典的な一般化としてはオイラーの定理があり、p を任意の法に、p−1 をオイラーのトーシェント関数 φ(n) に置き換えます。さらに読むには、入門書や上記の関連項目を参照してください。