フェルマーの小定理

概要

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

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

数学的帰納法による証明

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

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

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

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

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