モジュラ逆数について

個人的メモ

法 m における整数 a のモジュラ逆数 a^-1 (mod m) とは, aa^-1≡1 (mod m) を満たす a^-1≡x (mod m) なる整数 x の合同類である.

法 m における整数 a のモジュラ逆数が存在するための必要十分条件は gcd(m, a)=1 である.

a^-1 (mod m) を求める最も汎用的な方法は拡張されたユークリッドの互除法を用いることである. つまり, a, m が所与であるもとでの ax–qm=gcd(a,m)=1 を満たす x が a^-1 (mod m) である.

他にも, オイラーのトーシェント関数を用いて a^-1≡a^φ(m)-1 (mod m) としたり, カーマイケル関数を用いて a^-1≡a^λ(m)-1 (mod m) と求める方法があるが, これは m を因数分解する必要があるので効率的な導出方法ではない. これらの特殊形として, m が素数 p であった場合は, a^-1≡a^p-2 (mod p) とすることができる.

試しに 7^-1 (mod 15) を求めてみる. gcd(15,7)=1 であるから, このモジュラ逆数は確かに存在する.

ユークリッドの互除法による方法では, 7x-15q=1 を満たす x を求めればよい. 解のひとつに x=-2, q=-1 を得る. つまり, 7^-1≡(-2)≡13 (mod 15) である.

数論におけるオイラーの定理を利用する場合, φ(15)=8 であるから 7^-1≡7^8-1≡823543≡13 (mod 15) とできる. もっとも, 7⁷ を計算すると桁数が大きくなるので, 7⁷=7×7²×7⁴ と分解し(バイナリ法), それぞれの剰余をとってから計算すると桁数が少なくて済む.

カーマイケルの定理を利用する場合, λ(15)=4 であるから 7^-1≡7^4-1≡343≡13 (mod 15) とできる.