合同式の重要な定理である,フェルマーの小定理について解説します.
フェルマーの小定理: $p$ を素数,$a$ を $p$ と互いに素な整数とするとき,以下の等式が成り立つ. $$\large a^{p-1} \equiv 1 (mod\ p)$$
$a$ の $p-1$ 乗を $p$ で割った余りは $1$ になるということです.この定理を用いれば,たとえば, $$2^{6} \equiv 1 (mod\ 7), 3^{100} \equiv 1 (mod\ 101)$$ のように非常に大きな数の剰余がすぐに求められます.
実は,$p$ を素数,$n$ を任意の自然数とすると, $$n^p \equiv n (mod\ p)$$ が成り立ちます.もし,$n$ と $p$ が互いに素なら,両辺を $n$ で割ることができて,フェルマーの小定理の主張が得られます.したがって,以下では,『$p$ を素数,$n$ を任意の自然数とすると,$n^p \equiv n (mod\ p)$ が成り立つ』 という主張を証明します.
おそらく最も標準的な証明は数学的帰納法を用いる方法です.ポイントは,『$p$ を素数とすると,$1 \le k \le p-1$ の整数 $k$ に対して,${}_p \mathrm{C} _k$ は $p$ の倍数』ということです.
証明: $p$ を素数,$n$ を任意の自然数とすると,$n^p \equiv n (mod\ p)$ が成り立つことを $n$ に関する帰納法で示す.
$n=1$ のとき $$1^p \equiv 1 (mod\ p)$$ なので,OK.
$n=k+1$ のとき
$k^p \equiv k (mod\ p)$ が成り立つと仮定すると,二項定理より, $$(k+1)^p=k^p+{}_p \mathrm{C} _1 k^{p-1}+\cdots+{}_p \mathrm{C} _{p-1}k+1$$ ここで,$1 \le k \le p-1$ の整数 $k$ に対して,${}_p \mathrm{C} _k$ は $p$ の倍数なので, $$(k+1)^p \equiv k^p+1 \equiv k+1 (mod\ p)$$ よって,$n=k+1$ のときも主張が成立する.
組み合わせを用いた興味深い別証明を紹介します.例によって,示すべきことは,『$p$ を素数,$n$ を任意の自然数とすると,$n^p \equiv n (mod\ p)$ が成り立つ』 という主張です. $p$ を素数,$n$ を自然数とします.正 $p$ 角形の頂点を $n$ 色で塗ることを考えます.たとえば,下図は $p=3,\ n=2$ の場合に,すべての塗り方を列挙したものです.
まず,回転して同じ塗り方となるものもすべて区別すると,頂点の塗り方は全部で $n^p$ 通りあります.このうち,すべての頂点が同じ色で塗られているもの (それは $n$ 通りあります) を除いた $n^p-n$ 通りについて考えます.つまりこれら $n^p-n$ 通りの図形はすべて $2$ 色以上の色を用いて頂点が塗られているものです.いま,そのうちのひとつに着目すると,それを回転して得られる $p$ 個 (自分自身も含める) はすべて異なります.(もし同じものがあるとすると,$p$ が素数であることから,すべての頂点は同一の色で塗られていなければならない) したがって,$n^p-n$ 個は回転して同じ塗り方になる $p$ 個のかたまりに類別できます.したがって,$n^p-n$ は $p$ で割り切れます.
重要な定理なだけあって,他にも様々な証明が知られています.