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 = t_i-1 and bx = t_i, mod m. At the beginning, t₀ = m and t₁ = x. Therefore a = 0 and b = 1. Sure enough, ax = t₀ = 0, and bx = t₁ = 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;