## 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;
```