モジュラ逆数について

個人的メモ

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

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

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

他にも, オイラーのトーシェント関数を用いて a-1aφ(m)-1 (mod m) としたり, カーマイケル関数を用いて a-1aλ(m)-1 (mod m) と求める方法があるが, これは m を因数分解する必要があるので効率的な導出方法ではない. これらの特殊形として, m が素数 p であった場合は, a-1ap-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≡78-1≡823543≡13 (mod 15) とできる. もっとも, 77 を計算すると桁数が大きくなるので, 77=7×72×74 と分解し(バイナリ法), それぞれの剰余をとってから計算すると桁数が少なくて済む.

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

コメントを残す