$B3HD%%f!<%/%j%C%I$N8_=|K!(B(extended Euclid's algorithm)

$B#a(B $B$H(B $B#n(B $B$,8_$$$KAG!J$D$^$j(B GCD($B#a(B, $B#n(B) = 1) $B$G$"$l$P!"K!(B $B#n(B $B$K4X$9$k(B $B#a(B $B$N>hK!E*5U85!JN,$7$F5U?t$H$b8F$V!K$,B8:_$9$k!#$D$^$j!"(B

$B#a(B $B&V(B $B-q(B 1 (mod $B#n(B )

$B$rK~B-$9$k(B $B&V(B $B$,B8:_$9$k!#$3$N(B $B&V(B $B$r5a$a$k$N$OITEyJ}Dx<0(B $B#a(B $B&V(B + $B#n(B $B#y(B = 1 $B$r2r$/;v$K$[$+$J$i$:!"(B $B2<$K<($7$?%"%k%4%j%:%`$K$h$k2rK!$r(B $B3HD%%f!<%/%j%C%I$N8_=|K!(B(extended Euclid's algorithm) $B$H8F$V!#(B

long
modinv(a, n)
    long            a;
    long            n;
{
    long            q, s, t, u, v, w;

    s = a;
    t = n;
    u = 1;
    v = 0;

    while (s > 0) {
        q = t / s;
        w = t - q * s;
        t = s;
        s = w;
        w = v - q * u;
        v = u;
        u = w;
    }
    return ((v + n) % n);
}

See also $B%f!<%/%j%C%I$N8_=|K!(B