Calculating Modular Inverses

What is a modular inverse?

You are likely already very familiar with multiplicative inverses from the reals. Consider $a \in \mathbb{R}$. The inverse of this value can be denoted by $a^{-1} = \frac{1}{a}$ such that $a \cdot a^{-1} = 1$. The same concept applies to integers with respect to some modulus $m$. The inverse of an integer $b \in \mathbb{Z}_m$ satisfies the the equation $bb^{-1} \equiv 1 \pmod{m}$. This value $b^{-1}$ is called the modular inverse of $b\pmod{m}$.

Via the Extended Euclidean Algorithm

The Extended Euclidean Algorithm has two parts. In the first part we apply the standard Euclidean algorithm that one would use to find $\gcd{(a,b)}$ for two integers $a, b$. Then we reverse the process and use substitution to find an equation of the form $1 = ax + by$ for some integers $x, y$.

Example

Find $7^{-1} \pmod{26}$: First we apply the standard Euclidean algorithm as if we were trying to find $\gcd{(7,26)}$. Note that while doing this, if $\gcd(n,m) \not= 1$ then no inverse exists for $n \pmod{m}$.

Notice that we can rewrite equation $(3)$,

Let’s repeat this process of rewriting equations to represent their remainder and substitute them back into the equation:

$26(3) + 7(-11) = 1$ is the linear combination representing $\gcd{(7,26)} = 1$. From this we can derive the following two congruencies:

Therefore,

The Matrix Method

While the previous method works well, it can get a little complicated for large values and it becomes easy to make mistakes while performing the second portion of the operation. A simpler method is to use matrix interpretation of the algorithm. Essentially, we take the congruencies we found at above and put them in matrix form.

Solving this matrix using row addition will gives us the $gcd{(a,n)}$ and the values of $x, y$. However, since the value of $y$ is irrelevent to the inverse, we can safely ignore the last column and simplify further:

Let’s try to find $23^{-1} \pmod{101}$ with the matrix method. All we must do is plug the values $a = 23, n = 101$ into the above matrix and solve for $x$:

From this we find that $x = 22$ is a solution to the congruency $23x \equiv 1 \pmod{101}$. We can quickly verify the result to confirm that $23^{-1} \pmod{101} = 22$: