フェルマーの小定理
後になってレオンハルト・オイラーはこの定理を拡張し、 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} より、フェルマーの小定理に一致する。
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} は確率的素数」と出力して終了する。
すると、 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}}}
(証明終)