フェルマーの小定理
概要
\(p\) を素数とし、\(a\) を整数とすると下記が成り立つ。
\[
a^p \equiv a \quad (\textrm{mod} \quad p)
\]
また、\(p\) を素数とし、\(a\) を \(p\) の倍数でない (\(a, p\) が互いに素) のとするときに下記が成り立つ。
\[
a^{p - 1} \equiv 1 \quad (\textrm{mod} \quad p)
\]
応用
\(a, p\) が互いに素であれば mod \(p\) のにおいて \(a^{-1}\)(\(a\) の逆元) を求めることができる。
フェルマーの小定理より
\[\begin{split}
a \times a^{p - 2} &=1 \quad (\textrm{mod} \quad p)\\
\end{split}\]
両辺に\(a^{-1}\)を掛けると
\[\begin{split}
a^{p - 2} &=a^{-1} \quad (\textrm{mod} \quad p)\\
\end{split}\]
したがって mod \(p\) においては\(a\)の逆元は \(a^{p-2}\) となる。