フェルマーの小定理

定理

\(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^{-1} = a^{p-2}\]

ただし注意として \(a\) は \(p\) の倍数でない必要があり, 特に \(a = 0\) のときは使えない.