定理とその応用を紹介する. 定理の証明はしない.

フェルマーの小定理

\(p\) が素数で \(a\)\(p\) の倍数でない整数の時, \[a^{p-1} = 1 \mod p\]

逆数

\((\mathbb Z_p, \times)\) における逆数.

\(x = a^{p-2}\) とすれば, \(ax = xa = a^{p-1} = 1\) だから, \(x\)\(a\) の逆数である.

ただしもちろん \(a=0 \mod p\) のときは逆数は無い.