$a, m$を整数とするとき， \[ax \equiv 1 \pmod{m}\] となる$x$を$a$の（法$m$の）モジュラ逆数とよび，$a^{-1}$で表す。
$a$のモジュラ逆数が存在する必要十分条件は$\gcd(a,m)=1$である。
$p$を素数とし，法$p$でのモジュラ逆数を求める場合，フェルマーの小定理を利用できる。
フェルマーの小定理によれば$a\not\equiv 0\pmod{p}$のとき \[a^{p-1}\equiv 1\pmod{p}\] が成り立つので， \[a^{-1}\equiv a^{p-2}\pmod{p}\] である。
$a^{p-2}$は繰り返し二乗法を用いれば$O(\log p)$回程度の乗除算で求めることができる。
Pythonでは法$m$での$a^n$を，組込み関数powを使って，pow(a, n, m)で
計算できるので，
inva = pow(a, p-2, p)
とするだけでよい。
$a,m$は互いに素とする。$m$が素数でない場合は，オイラーの定理から \[a^{\phi(m)}\equiv 1\pmod{p}\] が成り立つので， \[a^{-1}\equiv a^{\phi(m)-1}\pmod{p}\] である。$\phi(m)$があらかじめ分かっている場合はこの方法でもよいが，一般に$\phi(m)$を求めるには$m$の素因数分解する程度の時間がかかるので，この方法は効率がよくない。
通常，モジュラ逆数を求める場合は，拡張ユークリッド互除法を利用して \[ax + my = 1\] の解を見つければ \[ax \equiv 1 - my \equiv 1 \pmod{m}\] なので，$x$が$a^{-1}$である。この方法でも$O(\log m)$回程度の乗除算が必要であるが，オイラーの定理を利用した繰り返し二乗法よりも平均的には高速である。
法10000で，$7^{-1}$を求めよ。
$\phi(m)=2^5\cdot 5^3=4000$であるから，$7^{3999}$を求めてもよいが，拡張ユークリッド互除法を使う。
class Main {
/**
* 法m における a の逆元
*/
static long inv(long a, long m) {
long r1 = a, r0 = m;
long x1 = 1, x0 = 0;
while (r1 != 0) {
long q = r0 / r1;
long v = r1;
r1 = r0 - q * r1;
r0 = v;
long w = x1;
x1 = x0 - q * x1;
x0 = w;
}
// ここでもし r_0 != 1 ならエラー処理をすべき
if (x0 < 0) {
x0 += m;
}
return x0;
}
public static void main(String[] args) {
System.out.println(inv(7, 10000));
}
}
def inv(a, m):
"""法 m における a の逆元
"""
r0, r1 = m, a
x0, x1 = 0, 1
while r1 != 0:
q = r0 // r1
r0, r1 = r1, r0 - q * r1
x0, x1 = x1, x0 - q * x1
# ここでもし r_0 != 1 ならエラー処理をすべき
if x0 < 0:
x0 += m
return x0
print(inv(7,10000))
print(pow(7,4000-1,10000)) #これもOK