となる i ,   j {\displaystyle i,\ j} (ただし、 i ≠ j {\displaystyle i\neq j} )が存在したとする。すると、 a {\displaystyle a} と p {\displaystyle p} が互いに素なので、 i ≡ j ( mod p ) {\displaystyle i\equiv j{\pmod {p}}} となり、 0 < i ,   j < p {\displaystyle 0<i,\ j<p} であることから、 i = j {\displaystyle i=j} となり、矛盾する。したがって、二つの集合は全体として合同であることが分かった。

それぞれの集合の要素をすべて掛け合わせると、 ( p − 1 ) ! ≡ ( p − 1 ) !   a p − 1 ( mod p ) {\displaystyle (p-1)!\equiv (p-1)!\ a^{p-1}{\pmod {p}}}

となる。 p {\displaystyle p} が素数であることから、 p {\displaystyle p} と ( p − 1 ) ! {\displaystyle \left(p-1\right)!} とは互いに素なので、 a p − 1 ≡ 1 ( mod p ) {\displaystyle a^{p-1}\equiv 1{\pmod {p}}}

（証明終）
オイラーの定理詳細は「オイラーの定理 (数論)」を参照

後になってレオンハルト・オイラーはこの定理を拡張し、 a {\displaystyle a} を n {\displaystyle n} と互いに素な整数とすると、 a φ ( n ) ≡ 1 ( mod n ) {\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}

が成り立つことを示した。ここで、 φ ( n ) {\displaystyle \varphi (n)} は n {\displaystyle n} 以下の n {\displaystyle n} と互いに素な自然数の個数を表し、オイラー関数と呼ばれる。

特に n {\displaystyle n} が素数のときは、 φ ( n ) = n − 1 {\displaystyle \varphi (n)=n-1} より、フェルマーの小定理に一致する。
カーマイケルの定理

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)} となるとは限らない。

たとえば、 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)}

n {\displaystyle n} が p 1 e 1 … p k e k {\displaystyle p_{1}^{e_{1}}\ldots p_{k}^{e_{k}}} と素因数分解できるなら、 λ ( p 1 e 1 ⋯ p k e k ) = lcm ⁡ { λ ( p 1 e 1 ) , … , λ ( p k e k ) } {\displaystyle \lambda (p_{1}^{e_{1}}\dotsb p_{k}^{e_{k}})=\operatorname {lcm} \{\lambda (p_{1}^{e_{1}}),\dotsc ,\lambda (p_{k}^{e_{k}})\}}

ここで lcm {\displaystyle \operatorname {lcm} } は最小公倍数。

カーマイケルの定理は、 a {\displaystyle a} と n {\displaystyle n} が互いに素なとき、 a λ ( n ) ≡ 1 ( mod n ) {\displaystyle a^{\lambda \left(n\right)}\equiv 1{\pmod {n}}}

が成り立つという定理である。

λ ( n ) {\displaystyle \lambda \left(n\right)} が n − 1 {\displaystyle n-1} の約数であるとき、 n {\displaystyle n} はカーマイケル数と呼ばれ、自身と互いに素であるようなすべての底でフェルマーテストを通過する絶対擬素数となる。
フェルマーテスト

フェルマーテストは、フェルマーの小定理の対偶を用いて確率的素数判定を行うアルゴリズムである。

フェルマーの小定理の対偶をとると、これは次のように、自然数 n が合成数であるための十分条件を与える。
対偶
n {\displaystyle n} と互いに素な整数 a {\displaystyle a} が a n − 1 ≢ 1 ( mod n ) {\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}} を満たせば、 n {\displaystyle n} は合成数である。

この十分条件を用いて、次のように自然数 n {\displaystyle n} の素数判定を行う。
パラメータとして、 2 {\displaystyle 2} 以上 n {\displaystyle n} 未満の自然数 a {\displaystyle a} を1つ定める。

a {\displaystyle a} と n {\displaystyle n} が互いに素でなければ「 n {\displaystyle n} は合成数」と出力して終了。

a n − 1 ≢ 1 ( mod n ) {\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}} ならば「 n {\displaystyle n} は合成数」と出力して終了する。そうでないとき「 n {\displaystyle n} は確率的素数」と出力して終了する。

フェルマーテストが「合成数」と出力したとき、上のフェルマーの小定理の対偶によって n {\displaystyle n} は実際に合成数である。しかし、上の対偶は十分条件を与えるのみで必要条件を与えるものではないので、「確率的素数」と出力された場合でも n {\displaystyle n} は実際に素数であるとは限らない。素数ではないにもかかわらず「確率的素数」と判定されてしまう合成数は擬素数と呼ばれる。