# Computing the Modular Inverse

When we're doing modular arithmetic, we need to use a different type of inverse to isolate terms. Suppose we have the equation,

$17x \equiv 1 \pmod{5} \,.$

If this were not in modulo $$5$$, we would simply divide both sides by $$17$$ yielding the solution of $$x$$ to be $$\frac{1}{17}$$. Unfortunately, that won't work for us this time, so we need to find the value of $$x$$ such that the product of $$17$$ and $$x$$ yields $$1$$ modulo $$5$$.

In Julia, we have a function which comes with the standard library, invmod which we can simply pass in $$17$$ and $$5$$ and get a result.

To get a better sense of what is happening under the hood, we'll handroll an implementation of invmod.

function myinvmod(a, m)
d, x, _ = gcdx(a, m)
d > 1 && throw(MethodError("Modular Inverse does not exist"))

mod(x, m)
end

We use the gcdx function which is the extended Euclidean algorithm which returns the $$\gcd(a, b)$$, the initial $$x$$ value and the initial $$y$$ value. If $$\gcd(a, b) \neq 1$$, then there is no modular inverse. Otherwise, we return $$x \mod{m}$$.

### Example

We want to find $$14^{-1} \pmod{17}$$, so we're looking for,

$14x \equiv 1 \pmod{17}\,,$

which we can write as,

$14X - 17Y = 1 \,.$

It's pretty obvious that $$\gcd(14, 17) = 1$$, but let's verify it.

\begin{aligned} 17 &= 14 \cdot 1 + 3 \\ 14 &= 3 \cdot 4 + 2 \\ 3 &= 2 \cdot 1 + \boxed{1} \\ 2 &= 1 \cdot 2 + 0 \end{aligned}

Working backwards now. We set $$a = 17$$ and $$b = 14$$.

\begin{aligned} 3 &= a - 1 \cdot b \\ \\ b &= (a - b)\cdot 4 + 2 \\ 2 &= b - (a - b)\cdot 4 \\ 1 &= a - 1 \cdot b - (b - 4(a - b)) \end{aligned}

Simplifying the last line,

$1 = a - b - b + 4a - 4b = 5a - 6b\,,$

which yields our final solution, $$14(-6) + 17(5) = 1$$ implying that $$X = -6$$ and $$Y = 5$$.

Finally, we want to compute $$-6 \equiv x \pmod{17}$$ which in this case is, $$-6 + 17 = 11$$.

We can verify this is the case as well by plugging $$11$$ back into our original equation to determine if $$11$$ is the modular inverse of $$14$$ modulo $$17$$. In fact, $$14 \cdot 11 = 154$$ and since $$17\cdot 9 = 153$$, we have indeed found our inverse.

@test myinvmod(14, 17) == 11
> Test Passed