フェルマーの小定理とは以下のような定理です:

定理 自然数$a$ 及び 素数$p$に対して $$ a^p \equiv a \pmod{p} $$ が成り立つ.

証明1. 初等的な方法

自然数$a$に対する数学的帰納法で示します.
$a=1$の場合は自明です.
$a=k$の時成り立ったと仮定して, $a=k+1$の場合を考えます. 二項定理より $$ (k+1)^p = k^p + 1 + \sum_{i=1}^{p-1} {}_{p}C_{i}k^i. $$ ここで $1 \le i \le p-1$の時 $$ {}_{p}C_{i} = \frac{p!}{i!(p-i)!} $$ の分母は$p$の倍数であり, 分子は$p$の倍数でないので ${}_{p}C_{i}$は$p$の倍数です. 以上と数学的帰納法の仮定より $$ \begin{align*} (k+1)^p &= k^p + 1 + \sum_{i=1}^{p-1} {}_{p}C_{i}k^i \\ &\equiv k^p + 1 \pmod{p} \\ &\equiv k + 1 \pmod{p}. \end{align*} $$ 以上によって, 数学的帰納法によって 題意は示された.

証明2. 群論を使った証明

群$G$とその部分群$H$に対して $H$の位数は$G$の位数の約数になるのでした.

ここで $G = \ZZ/p\ZZ, H= \langle a \rangle \subset G$と置きます.

すると 主張を得ます.