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