フェルマーの小定理

どこかの予備講師が授業終了前10分で証明してたと聞いたことがあって、俺もやりたくなった。

素数 $p$ の倍数でない整数 $a$ に対し, $a ^ {p-1} \equiv 1\ \mathrm{mod}\ p.$

（証明） $k = 1, \cdots, p-1$ に対して $ka$ を $p$ で割った余りを $r _ k$ とするとき, $ka$ は $p$ で割り切れないので, $1 \leqq r _ k \leqq p-1.$

次に, $r _ 1, \cdots, r _ {p-1}$ が相異なることを示す: $i \neq j$ ならば $r _ i \neq r _ j$ .

対偶を示す. $r _ i = r _ j$ なら $ia \equiv ja \Leftrightarrow a(i-j) \equiv 0\ \mathrm{mod}\ p$ で, $a$ と $p$ は互いに素だから $i - j \equiv 0 \Leftrightarrow i \equiv j\ \mathrm{mod}\ p$ となるが, $1 \leqq i, j \leqq p-1$ だから $i=j$ .