フェルマーの小定理
補題から、 ( k + 1 ) p {\displaystyle \left(k+1\right)^{p}} を p {\displaystyle p} で割った余りは k p + 1 {\displaystyle k^{p}+1} を p {\displaystyle p} で割った余りに等しい。帰納法の仮定によって k p {\displaystyle k^{p}} を p {\displaystyle p} で割った余りは k {\displaystyle k} を p {\displaystyle p} で割った余りに等しいから、 ( k + 1 ) p {\displaystyle \left(k+1\right)^{p}} を p {\displaystyle p} で割った余りは k + 1 {\displaystyle k+1} を p {\displaystyle p} で割った余りに等しい。
したがって、命題は a = k + 1 {\displaystyle a=k+1} のときも成り立つ。
数学的帰納法によって、命題は a ≧ 2 {\displaystyle a\geqq 2} に対して成り立つ。また、 a = 0 , 1 {\displaystyle a=0,\ 1} のときは、代入してみると明らかに成り立つので、命題は a ≧ 0 {\displaystyle a\geqq 0} に対して成り立つ。
(証明終)
たとえば、 n = 10000 {\displaystyle n=10000} のとき、カーマイケルの定理によれば n {\displaystyle n} と互いに素なすべての a {\displaystyle a} に対して a m ≡ 1 ( mod n ) {\displaystyle a^{m}\equiv 1{\pmod {n}}} を満たす最小の m {\displaystyle m} は500であるが、特定の a = 7 {\displaystyle a=7} に対しては 7 100 ≡ 1 ( mod n ) {\displaystyle 7^{100}\equiv 1{\pmod {n}}} が成立する。
カーマイケル関数(英語版) λ ( n ) {\displaystyle \lambda \left(n\right)} を以下のように再帰的に定義する。
n = 2 e {\displaystyle n=2^{e}} なら、
λ ( 2 e ) = { 1 ( e = 1 ) 2 ( e = 2 ) 2 e − 2 ( e ≥ 3 ) {\displaystyle \lambda (2^{e})={\begin{cases}1&(e=1)\\2&(e=2)\\2^{e-2}&(e\geq 3)\end{cases}}}
n {\displaystyle n} が奇素数 p {\displaystyle p} を用いて n = p e {\displaystyle n=p^{e}} と書けるなら、
λ ( p e ) = p e − 1 ( p − 1 ) {\displaystyle \lambda (p^{e})=p^{e-1}(p-1)}
数論において、フェルマーの小定理(フェルマーのしょうていり、英: Fermat's little theorem)は、素数の性質についての定理であり、実用としてもRSA暗号に応用されている定理である。