合同式の重要な定理である，フェルマーの小定理について解説します．
フェルマーの小定理: $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$ で割り切れます．
重要な定理なだけあって，他にも様々な証明が知られています．
