Modular Mathematics, Finding the Inverse

Finding the Inverse

To find the inverse of x mod m, solve yx + km = 1.  Thus y is the inverse of x.  You can use Euclid's gcd algorithm with backtracking, but that requires a stack.  Since we don't care about k, and we only need to know y mod m, there is an easier way.

Apply the gcd algorithm to x and m, until you finally reach 1.  If the gcd is not 1, x is not invertible mod m.  At each step of the algorithm, we maintain two new variables a and b, such that ax = ti-1 and bx = ti, mod m.  At the beginning, t0 = m and t1 = x.  Therefore a = 0 and b = 1.  Sure enough, ax = t0 = 0, and bx = t1 = x.  At each step, the values of t shift, hence a is set to b.  At the same time, b becomes a-qb, where q is the quotient produced by the gcd algorithm.  Of course a and b are reduced mod m after each step.  Here is some code.

s = m, t = x; /* set up for gcd(x,m) */
a = 0, b = 1; /* 0*x = s and 1*x = t */
while(t) {
    q = s/t, r = s%t; /* quotient and remainder */
    s = t, t = r; /* push back */
    temp = (a-b*q) % m;
    a = b, b = temp; /* push back */
}
return a;