フェルマーの小定理
Fermat's little theorem
$ p が素数、$ a を任意の整数とすると:
$ a^p \equiv a \pmod p が成り立つ
特に$ p が$ a の因数でない場合は:
$ a^{p-1} \equiv 1 \pmod p が成り立つ
合成数であるかを判定できる
$ n>1 が与えられたとき、$ a>1 を選び、$ n を法として$ a^{n-1} を計算する
$ a^{n-1} \not\equiv 1 \pmod n ならば、$ n は合成数である