フェルマーの小定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』

数論において、フェルマーの小定理は素数の性質についての定理であり、実用としてもRSA暗号に応用されている定理である。

目次 1 概要 2 証明 3 オイラーの定理 4 フェルマーテスト 5 一般化 6 参考文献 7 外部リンク

[編集] 概要

p を素数とし、a を p の倍数でない整数（a と p は互いに素）とするときに、

すなわち a を p - 1 乗したものを p で割ったあまりは 1 になるというもの。有名なフェルマーの最終定理と区別するためにあえて「小」定理と称されている。

この定理はピエール・ド・フェルマーの名を冠するが、フェルマーの他の予想と同じく、フェルマー自身によって証明が与えられていたことが確認されているわけではない。この定理に対する証明はゴットフリート・ライプニッツによって初めて与えられた。

[編集] 証明

二項式の累乗を展開する公式から、数学的帰納法を用いて証明する方法が簡便である。ここでは、

つまり aを p 乗したものを p で割ったあまりは a を p で割ったあまりに等しいという形の命題として証明する。

1. (m + 1)^p という式を展開することを考える。これは公式により、
   m^p + _pC₁m^p-1 + _pC₂m^p-2 + … + _pC_p-1m + 1
   となる。
2. ここで両端の項以外はすべての項に _pC_k が因数として含まれている。これは、p が素数であれば k が 1 以上 p 未満である限り必ず p で割り切れる。なぜなら _pC_k = p!/(p-k)!k! であり、p が素数であるなら分子には p が含まれているものの分母に p やその倍数は含まれないからである。
3. すると、両端の項以外は p で割り切れる。(m + 1)^p を p で割ったあまりは、残る m^p + 1 を p で割ったあまりと等しいことになる。
4. ここで、m = 1 とする。2^p = (1 + 1)^p を p で割ったあまりは 1^p + 1 = 2 ということになり、命題は a = 2 の場合に正しいことが証明された。
5. a に関する帰納法で示すために、a = k で命題が成立していると仮定する。ステップ3により、(k + 1)^p を p で割ったあまりは、k^p + 1 を p で割ったあまりに等しい。さらにこれは、帰納法の仮定により、k + 1 を p で割ったあまりに等しい。したがって命題は a = k + 1 でも成立する。数学的帰納法によって 2 以上のすべての a について命題は成立することになる。
6. a = 0, 1 の場合は命題の成立することが自明。

（証明終わり）

[編集] オイラーの定理

後になってレオンハルト・オイラーはこの定理を拡張し、a を n と互いに素な整数とするときに、

が成り立つことを示した。ここで、は n 未満の n に素な自然数の個数を表し、オイラー関数 と呼ばれる。

n が素数のときに限れば、 であるからこれはフェルマーの小定理に一致する。

[編集] フェルマーテスト

フェルマーテストは、 フェルマーの小定理の対偶を用いて確率的素数判定を行うアルゴリズムである。

フェルマーの小定理の対偶をとると、これは次のように、自然数 n が合成数であるための十分条件を与える。

対偶

n と互いに素な 整数 a が

を満たせば、このとき n は合成数である。

この十分条件を用いて、次のように自然数 n の素数判定を行う。

1. パラメータとして、2 以上 n 未満の自然数 a を1つ定める。
2. a と n が互いに素でなければ「n は合成数」と出力して終了。
3. ならば「n は合成数」と出力して終了する。
   そうでないとき「n は確率的素数」と出力して終了する。

フェルマーテストが「合成数」と出力したとき、上のフェルマーの小定理の対偶によって n は実際に合成数である。しかし、上の対偶は十分条件を与えるのみで必要条件を与えるものではないので、「確率的素数」と出力された場合でも n は実際に素数であるとは限らない。素数ではないにもかかわらず「確率的素数」と判定されてしまう自然数は擬素数と呼ばれる。

疑わしければ、「確率的素数」と出力された場合にはまた異なる a を用いて再びテストを行う。十分な回数だけ a を取り替えて繰り返せば、フェルマーテストが「確率的素数」と判定した数は実際に素数である可能性が高い。

しかし、カーマイケル数または絶対擬素数と呼ばれる "反例" もある。カーマイケル数は、合成数であるにも関わらずいかなる a を用いても「確率的素数」と判定されてしまう( a がカーマイケル数の素因数であるときのみ合成数と判定される)。従って、フェルマーテストは完全な素数判定法ではない。10000 以下のカーマイケル数は 561, 1105, 1729, 2465, 2821, 6601, 8911 である。カーマイケル数は無限個存在することが知られている。

フェルマーテストを改善するアルゴリズムとしては、ラビン-ミラー素数判定法やAKS素数判定法がある。

[編集] 一般化

フェルマーの小定理・オイラーの定理は一般の有限群の定理に拡張できる。G を位数 m の有限群とすると、G の任意の元 g に対して g^m は単位元に一致する。オイラーの定理は G が乗法群 (Z/nZ)^× のときの場合であり、フェルマーの小定理はさらに n が素数の場合である。

[編集] 参考文献

• 高木貞治『初等整数論講義〈第2版〉』共立出版、1971年、67頁、53-54頁。ISBN 4-320-01001-9
• G.H.ハーディ、E.M.ライト『数論入門Ⅰ』シュプリンガー・フェアラーク東京、2001年、82-107頁。ISBN 4-431-70848-0

[編集] 外部リンク

• Eric W. Weisstein. Fermat's Little Theorem., MathWorld.（英語）