一見すると作為的に思えるこの関係式が、一体なぜいかなる素数においても例外なく成り立つのでしょうか。フェルマーの小定理の背後には、数学が持つ極めてエレガントな秩序が存在します。代表的な2つの証明アプローチからそのロジックを紐解きます。
アプローチ1：剰余類の置換を利用した鮮やかな証明
最も直感的で美しいとされるのが、集合の並び替えを利用する手法です。素数 $p$ で割ったときの 0 以外の余りは、必ず $\{1, 2, 3, \dots, p-1\}$ の $p-1$ 種類になります。この集合の各要素に、素数 $p$ と互いに素な整数 $a$ を掛け合わせた次の数列を考えます。
$$S = \{1a, 2a, 3a, \dots, (p-1)a\}$$
ここで重要なのは、この $S$ に含まれる数同士を $p$ で割った余りは、すべて互いに異なり、重複が一切発生しないという点です。もし仮に $ka \equiv ma \pmod p$（$1 \le k < m \le p-1$）が成り立ったとすると、$(m - k)a$ は $p$ の倍数となります。しかし $a$ は $p$ と互いに素であり、$m - k$ は $p$ より小さい正の整数であるため、$p$ の倍数にはなり得ず矛盾します。
すなわち、$S$ の要素を $p$ で割った余りは、元の $\{1, 2, 3, \dots, p-1\}$ の順番をただシャッフルして並び替えたものに過ぎません。したがって、両方の集合の全要素を掛け合わせた積は、$\pmod p$ において一致します。
$$(1a) \times (2a) \times (3a) \times \dots \times ((p-1)a) \equiv 1 \times 2 \times 3 \times \dots \times (p-1) \pmod p$$
左辺を整理すると $a$ が $p-1$ 個存在し、階乗 $(p-1)!$ が現れます。
$$a^{p-1} (p-1)! \equiv (p-1)! \pmod p$$
$p$ は素数であるため、1 から $p-1$ までの積である $(p-1)!$ は $p$ と互いに素です。したがって両辺を $(p-1)!$ で割ることが許され、鮮やかに目標の式が導き出されます。
$$a^{p-1} \equiv 1 \pmod p$$
アプローチ2：二項定理と数学的帰納法による代数的アプローチ
もう一つの王道の道筋が、高校数学の範囲でも完全に追体験可能な二項定理と数学的帰納法を用いたアプローチです。目標はすべての自然数 $a$ について $a^p \equiv a \pmod p$ を示すことです。
まず二項展開の公式を用いて $(a + 1)^p$ を分解します。
$$(a + 1)^p = a^p + \binom{p}{1}a^{p-1} + \binom{p}{2}a^{p-2} + \dots + \binom{p}{p-1}a + 1$$
ここで着目すべきは途中に現れる二項係数 $\binom{p}{k} = \frac{p!}{k!(p-k)!}$（$1 \le k \le p-1$）です。分子には素数 $p$ が含まれ、分母の $k!$ や $(p-k)!$ には $p$ 未満の数しか存在しないため、$p$ を約分して消すことができません。つまり、両端の項を除くすべての係数は $p$ の倍数になります。したがって、mod $p$ の世界では間の項がすべて綺麗に消失します。
$$(a + 1)^p \equiv a^p + 1 \pmod p$$
$a = 1$ のとき $1^p = 1$ より明らかに成立します。$a = k$ で $k^p \equiv k \pmod p$ が成り立つと仮定すると、$(k + 1)^p \equiv k^p + 1 \equiv k + 1 \pmod p$ となり、$a = k + 1$ でも成立します。数学的帰納法により、すべての自然数 $a$ において $a^p \equiv a \pmod p$ が証明されます。
