フェルマーの小定理

概要

フェルマーの小定理
pが素数、aが任意の自然数のとき、
$a^{p}\equiv a{\bmod {p}}$
特に、pが素数で、aがpと互いに素な自然数のとき、
$a^{p-1}\equiv 1{\bmod {p}}$

定理の前提条件(pが素数、aがpと互いに素な整数のとき)も重要である。

数学的帰納法による証明

aに関する数学的帰納法を用いて、$a^{p}\equiv a{\bmod {p}}$を証明する。
aとpが互いに素なとき、合同式の両辺をaで除算することができるので、フェルマーの小定理が導かれる。

証明
$a=1$のとき、$1^{p}\equiv 1{\bmod {p}}$
また、二項定理を用いることで、
$(m+1)^{p}=m^{p}+1+\sum _{k=1}^{p-1}pC_{k}m^{k}\equiv m^{p}+1$
(pが素数で$1\leq k\leq p-1$のとき、$_{p}C_{k}={\frac {p(p-1)\cdots (p-k+1)}{k!}}$がpの倍数であることを用いた)
よって、$m^{p}\equiv m{\bmod {p}}$なら、$(m+1)^{p}\equiv m+1$
以上から、数学的帰納法より、全てのaに対して$a^{p}\equiv a{\bmod {p}}$
よって、pとaが互いに素なとき、両辺をaで除算してフェルマーの小定理を得る。

整数の有名な性質を利用した証明

整数の有名な定理"aとpが互いに素なとき、$a,2a,3a,\cdots ,(p-1)a$をpで除算した余りは全て異なる"ということを用いる。
この定理を知らない人は、1次不定方程式$ax+by=c$の整数解の真ん中あたりで証明しているので参考にする。

証明
$a,2a,3a,\cdots ,(p-1)a$は全てpの倍数ではないので、
$a,2a,3a,\cdots ,(p-1)a$をpで除算した余りを並べると、1からp − 1までが全て1度ずつ登場する。
よって、$a\times 2a\times 3a\times \cdots \times (p-1)a\equiv (p-1)!$
ここで、$(p-1)!$はpと互いに素なので、両辺を</math>(p - 1)!</math>で除算して、$a^{p}-1\equiv 1$を得る。