フェルマーの小定理

フェルマーの小定理とは、以下の定理のことです。

ある正の整数\(a\)と素数\(p\)について、\(a\)が\(p\)で割り切れない場合、次の合同が成り立ちます。

\[a^{p-1} \equiv 1 \pmod{p}\]

つまり、\(a^{p-1}\)を\(p\)で割った余りは常に1です。