フェルマーの小定理
フェルマーの小定理・オイラーの定理は一般の有限群の定理に拡張できる。 G {\displaystyle G} を位数 m {\displaystyle m} の有限群とすると、 G {\displaystyle G} の任意の元 g {\displaystyle g} に対して g m {\displaystyle g^{m}} は単位元に一致する。オイラーの定理は G {\displaystyle G} が乗法群 ( Z / n Z ) × {\displaystyle \left(\mathbb {Z} /n\mathbb {Z} \right)^{\times }} のときの場合であり、フェルマーの小定理はさらに n {\displaystyle n} が素数の場合である。
二項定理から、数学的帰納法を用いて証明する方法が簡便である。
補題:「 ( m + 1 ) p {\displaystyle \left(m+1\right)^{p}} を p {\displaystyle p} で割った余りは m p + 1 {\displaystyle m^{p}+1} を p {\displaystyle p} で割った余りに等しい。」
(補題の証明)
( m + 1 ) p = m p + p C 1 m p − 1 + p C 2 m p − 2 + ⋯ + p C p − 1 m + 1 {\displaystyle (m+1)^{p}=m^{p}+{}_{p}\mathrm {C} _{1}m^{p-1}+{}_{p}\mathrm {C} _{2}m^{p-2}+\dotsb +{}_{p}\mathrm {C} _{p-1}m+1} (二項定理)
右辺の両端以外の二項係数 p C k {\displaystyle {}_{p}\mathrm {C} _{k}} はすべて p {\displaystyle p} の倍数である。なぜなら、
p C k = p ( p − 1 ) ⋯ ( p − k + 1 ) k ( k − 1 ) ⋯ 1 {\displaystyle {}_{p}\mathrm {C} _{k}={\frac {p(p-1)\dotsb (p-k+1)}{k(k-1)\dotsb 1}}}