フェルマーの小定理
であり、 p {\displaystyle p} は素数であって k < p {\displaystyle k<p} なので、分子に含まれる p {\displaystyle p} が約分されることはないからである。
したがって、 ( m + 1 ) p {\displaystyle \left(m+1\right)^{p}} を p {\displaystyle p} で割った余りは、両端の項 m p + 1 {\displaystyle m^{p}+1} を p {\displaystyle p} で割った余りに等しい。(補題の証明終)
命題「 a p ≡ a ( mod p ) {\displaystyle a^{p}\equiv a{\pmod {p}}} 」を、 a {\displaystyle a} についての数学的帰納法で証明する。
補題に m = 1 {\displaystyle m=1} を代入すると、 2 p = ( 1 + 1 ) p {\displaystyle 2^{p}=\left(1+1\right)^{p}} を p {\displaystyle p} で割った余りは 1 p + 1 = 2 {\displaystyle 1^{p}+1=2} となり、 a = 2 {\displaystyle a=2} のとき成り立つ。
命題が、 a = k {\displaystyle a=k} のとき成り立つと仮定する。
m = φ ( n ) {\displaystyle m=\varphi (n)} とすれば、 a m ≡ 1 ( mod n ) {\displaystyle a^{m}\equiv 1{\pmod {n}}} が n {\displaystyle n} と互いに素なすべての a {\displaystyle a} に対して成り立つが、 φ ( n ) {\displaystyle \varphi (n)} はこの性質を満たす m {\displaystyle m} の最小の数とは限らない。カーマイケルの定理はオイラーの定理を精緻化したもので、すべての a {\displaystyle a} に対して a m ≡ 1 ( mod n ) {\displaystyle a^{m}\equiv 1{\pmod {n}}} が成立するような最小の m {\displaystyle m} を与える。ただし、 n {\displaystyle n} と互いに素な a {\displaystyle a} が与えられたときに、 a m ≡ 1 ( mod n ) {\displaystyle a^{m}\equiv 1{\pmod {n}}} を満たす最小の m {\displaystyle m} は、 λ ( n ) {\displaystyle \lambda \left(n\right)} となるとは限らない。