数論において、フェルマーの小定理（フェルマーのしょうていり、Fermat's little theorem）は素数の性質についての定理であり、実用としてもRSA暗号に応用されている定理である。"p" を素数とし、"a" を "p" の倍数でない整数（"a" と "p" は互いに素）とするときに、すなわち、"a" の "p" − 1 乗を "p" で割った余りは 1 であるというもの。有名なフェルマーの最終定理と区別するためにあえて「小」定理と称されている。この定理はピエール・ド・フェルマーの名を冠するが、フェルマーの他の予想と同じく、フェルマー自身によって証明が与えられていたことが確認されているわけではない。この定理に対する証明はゴットフリート・ライプニッツによって初めて与えられた。二項定理から、数学的帰納法を用いて証明する方法が簡便である。元の定理はと同値である（"a" と "p" は互いに素より、両辺を "a" で割れるから）。この形の命題として証明する。補題：「("m" + 1) を "p" で割った余りは "m" + 1 を "p" で割った余りに等しい。」（補題の証明）右辺の両端以外の二項係数 C は全て "p" の倍数である。なぜなら、であり、"p" は素数で、"k" < "p" より、分子に含まれる "p" は約分されることはないからである。ゆえに、("m" + 1) を "p" で割った余りは、両端の項 "m" + 1 を "p" で割った余りに等しい。（補題の証明終）「"a" ≡ "a" (mod "p")」を "a" に関する数学的帰納法で証明する。補題に "m" = 1 を代入すると、2 = (1 + 1) を "p" で割った余りは 1 + 1 = 2 となり、"a" = 2 のとき成り立つ。"a" = "k" のとき成り立つと仮定する。補題より、("k" + 1) を "p" で割った余りは "k" + 1 を "p" で割った余りに等しい。帰納法の仮定により "k" を "p" で割った余りは "k" を "p" で割った余りに等しいから、これは "k" + 1 を "p" で割った余りに等しい。ゆえに "a" = "k" + 1 のときも成り立つ。ゆえに帰納法により "a" ≧ 2 に対して成り立つが、"a" = 0, 1 のときも、代入してみると明らかに成り立つ。（証明終）上の補題と同様に、("x" + "y") ≡ "x" + "y" (mod "p") が示せる。これより、
"a" = {1 + (1 + 1 + … + 1)}
　　≡ 1 + {1 + (1 + 1 + … + 1)}
　　≡ …
　　≡ 1 + 1 + … + 1
　　≡ "a" (mod "p")
ここで "a" と "p" は互いに素なので、両辺を "a" で割ることができ、
"a" ≡ 1 (mod "p")
となる。（証明終）"ia" ≡ "ja" (mod "p")なる"i

出典:wikipedia