フェルマーの小定理

数論において、フェルマーの小定理（フェルマーのしょうていり、）は、素数の性質についての定理であり、実用としてもRSA暗号に応用されている定理である。
概要.
formula_1 を素数とし、 formula_2 を整数とすると、
が成立すると言う定理である。また、 formula_1 を素数とし、 formula_2 を formula_1 の倍数でない整数（ formula_2 と formula_1 は互いに素）とするときに、
が成立する。すなわち、 formula_2 の formula_11 乗を formula_1 で割った余りは formula_13 である。有名なフェルマーの最終定理と区別するためにあえて「小」定理と称されている。
この定理はピエール・ド・フェルマーの名を冠するが、フェルマーの他の予想と同じく、フェルマー自身によって証明が与えられていたことが確認されているわけではない。この定理に対する証明はゴットフリート・ライプニッツによって初めて与えられた。
証明.
3通りの証明を示す。
証明(1).
二項定理から、数学的帰納法を用いて証明する方法が簡便である。
補題：「 formula_14 を formula_1 で割った余りは formula_16 を formula_1 で割った余りに等しい。」
（補題の証明）
右辺の両端以外の二項係数 formula_19 はすべて formula_1 の倍数である。なぜなら、
であり、 formula_1 は素数であって <math>k なので、分子に含まれる formula_1 が約分されることはないからである。
したがって、 formula_14 を formula_1 で割った余りは、両端の項 formula_16 を formula_1 で割った余りに等しい。（補題の証明終）
命題「 formula_28 」を、 formula_2 についての数学的帰納法で証明する。
補題に formula_30 を代入すると、 formula_31 を formula_1 で割った余りは formula_33 となり、 formula_34 のとき成り立つ。
命題が、 formula_35 のとき成り立つと仮定する。
補題から、 formula_36 を formula_1 で割った余りは formula_38 を formula_1 で割った余りに等しい。帰納法の仮定によって formula_40 を formula_1 で割った余りは formula_42 を formula_1 で割った余りに等しいから、 formula_36 を formula_1 で割った余りは formula_46 を formula_1 で割った余りに等しい。
したがって、命題は formula_48 のときも成り立つ。
数学的帰納法によって、命題は formula_49 に対して成り立つ。また、 formula_50 のときは、代入してみると明らかに成り立つので、命題は formula_51 に対して成り立つ。
（証明終）
証明(2).
上の補題と同様に、formula_52 が示せる。これより、
（証明終）
証明(3).
formula_1 を素数とし、 formula_2 と formula_1 が互いに素とするときに、
が成立することを、ここで証明する。
集合 formula_58 は、全体として法 formula_1 の下で formula_60 と合同である。（背理法による証明）もし後者の集合内に
となる formula_62 (ただし、 formula_63 )が存在したとする。すると、 formula_2 と formula_1 が互いに素なので、 formula_66 となり、 formula_67 となり、矛盾する。したがって、二つの集合は全体として合同であることが分かった。
それぞれの集合の要素をすべて掛け合わせると、
となる。 formula_1 が素数であることから、 formula_1 と formula_71 とは互いに素なので、
（証明終）
オイラーの定理.
後になってレオンハルト・オイラーはこの定理を拡張し、 formula_2 を formula_74 と互いに素な整数とすると、
が成り立つことを示した。ここで、formula_76 は formula_74 未満の formula_74 と互いに素な自然数の個数を表し、"オイラー関数"と呼ばれる。
特に formula_74 が素数のときは、formula_80 より、フェルマーの小定理に一致する。
カーマイケルの定理.
formula_81 とすれば、 formula_82 が formula_74 と互いに素なすべての formula_2 に対して成り立つが、 formula_76 はこの性質を満たす formula_86 の最小の数とは限らない。カーマイケルの定理はオイラーの定理を精緻化したもので、最小の formula_86 を与える。
 formula_88 を以下のように再帰的に定義する。
formula_89 なら、
formula_74 が奇素数 formula_1 を用いて formula_93 と書けるなら、
formula_74 が formula_96 と素因数分解できるなら、
ここで formula_98 は最小公倍数。 
カーマイケルの定理は、 formula_2 と formula_74 が互いに素なとき、
が成り立つという定理である。
formula_88 が formula_103 の約数であるとき、 formula_74 はカーマイケル数と呼ばれ、自身と互いに素であるようなすべての底でフェルマーテストを通過する絶対擬素数となる。
フェルマーテスト.
フェルマーテストは、フェルマーの小定理の対偶を用いて確率的素数判定を行うアルゴリズムである。
フェルマーの小定理の対偶をとると、これは次のように、自然数 "n" が合成数であるための十分条件を与える。
この十分条件を用いて、次のように自然数 formula_74 の素数判定を行う。
フェルマーテストが「合成数」と出力したとき、上のフェルマーの小定理の対偶によって formula_74 は実際に合成数である。しかし、上の対偶は十分条件を与えるのみで必要条件を与えるものではないので、「確率的素数」と出力された場合でも formula_74 は実際に素数であるとは限らない。素数ではないにもかかわらず「確率的素数」と判定されてしまう合成数は擬素数と呼ばれる。
疑わしければ、「確率的素数」と出力された場合にはまた異なる formula_2 を用いて再びテストを行う。十分な回数だけ formula_2 を取り替えて繰り返せば、フェルマーテストが「確率的素数」と判定した数は実際に素数である可能性が高い。
しかし、カーマイケル数または絶対擬素数と呼ばれる "反例" もある。カーマイケル数は合成数であるにもかかわらず、ほとんどいかなる formula_2 を用いても「確率的素数」と判定されてしまう。従って、フェルマーテストは完全な素数判定法ではない。
フェルマーテストを改善するアルゴリズムとしては、ミラー–ラビン素数判定法やAKS素数判定法がある。
一般化.
フェルマーの小定理・オイラーの定理は一般の有限群の定理に拡張できる。 formula_124 を位数 formula_86 の有限群とすると、 formula_124 の任意の元 formula_127 に対して formula_128 は単位元に一致する。オイラーの定理は formula_124 が乗法群 formula_130 のときの場合であり、フェルマーの小定理はさらに formula_74 が素数の場合である。