Inverse

The next operation we want to discuss is the inverse operation. The inverse of addition is subtraction, which can be done easily. But the concept of multiplicative inverse in modular arithmetic is less clear (for real numbers, the inverse of $x$ is simply $1/x$). Being able to compute an inverse is important in many algorithmic applications, and we will cover the theories behind it.

We say that $x$ is a multiplicative inverse of $a$ modulo $m$ if $ax \equiv 1 \pmod{m}$. Does an inverse always exist? Let us try some simple examples.

Example 18

When $m=5$, every nonzero number has an inverse. Inverses of $1,2,3,4$ are $1,3,2,4$ respectively. When $m=4$, notice that $2$ and $4$ do not have an inverse, while $1$ and $3$ do (inverses are $1$ and $3$ respectively).

Let us start with a simple observation, which is easy to prove.

Exercise 47

If $a$ has a multiplicative inverse modulo $m$, then ${\sf gcd}(a,m) = 1$.

So we know that ${\sf gcd}(a,m) =1$ is necessary for the existence of an inverse. It turns out that this is also sufficient.

Lemma 10

If ${\sf gcd}(a,m) =1$, then $a$ has a unique multiplicative inverse modulo $m$.

Proof:

Consider multiplying $a$ by every number in modulo $m$ (i.e., $0,\ldots, m-1$). So, we get $0, a, 2a, \ldots, (m-1)a$. We claim that these numbers are all distinct under modulo $m$. Assume for contradiction that $a x \equiv ay \pmod{m}$ for $m-1 \ge x > y \ge 0$. This would imply that $m \mid (x-y)a$ or $m q = (x-y)a$ for some $q$. Since $m$ and $a$ do not share any common divisor (greater than $1$), we know that $m \mid (x-y)$, a contradiction since $x-y$ ranges between $1$ and $m-1$.

The uniqueness of inverses allows us to write things like $a^{-1} \pmod{m}$. If we did not know uniqueness, such notation would not make sense.

Now we present an algorithm that computes the multiplicative inverse of $a$ modulo $m$. Before going into an abstract setting, let us look at a simple example on how to derive an inverse. Let us try to compute the inverse of $12$ modulo $35$. Let $x$ be an inverse (we know it exists). We set up two equations that we know:

$35x \equiv 0 \pmod{35}, 12x \equiv 1 \pmod{35}$

By subtracting twice the second equation from the first, we have:

$11 x \equiv -2 \pmod{35}$

By subtracting this one from the above,

$x \equiv 3 \pmod{35}$

At this point, let us warn the students that such derivations (by manipulating the equations) in general may not necessarily find a solution. The derivation gives us a necessary condition that, if an inverse exists, it must be equal to $3$ under modulo $35$. This fact, in combination with the existence of the inverse (guaranteed by Lemma 10), implies that $3$ is an inverse and the only one (modulo $35$). The lesson here is that such derivations alone do not always find all solutions we are looking for: It is the combination between mathematical derivation and the existential theorem that allows us to make a conclusion.

Now, let us turn the above example into a more general algorithm, which finds $a^{-1} \pmod{m}$, provided this exists.

$\mathrm{Inverse}(a,m)$

1. $A\leftarrow a, B \leftarrow m, C \leftarrow 1, D \leftarrow 0$.
2. while $B\geq 1$ do
   1. $R \leftarrow A \pmod{B}$
   2. $A \leftarrow B$, $B \leftarrow R$, $C \leftarrow D$ and $D \leftarrow C - D \cdot \lfloor A/B\rfloor$
3. return $C$

Notice the simplicity of the above algorithm and its similarity to the Euclid's algorithm for computing the greatest common divisor. Its correctness follows from a simple loop invariant:

Theorem 17

Let $x$ be the multiplicative inverse $a^{-1}$. The following is loop invariant:

$Ax \equiv C \pmod{m} \text{ and } B x \equiv D \pmod{m}$

Notice that this loop invariant implies the correctness of our algorithm. First it holds before the algorithm enters the loop since we have $a x \equiv 1 \pmod{m}$ (here we use the existence of the inverse) and $mx \equiv 0 \pmod{m}$. When the algorithm terminates, we have that $A= 1$ and $B=0$, so by the loop invariant, $x \equiv C \pmod{m}$ as desired.

Proof:

Assume that the statement holds before entering the loop. Let $A',B',C',D'$ be the values of $A,B,C,D$ after the end of the loop. The loop made the update so that $A' = B$ and $C'=D$, so we have that $A' x \equiv C'\pmod{m}$. Notice that $B'=R = A - B \cdot \lfloor A/B\rfloor$. By multiplying $B x \equiv D \pmod{m}$ by $\lfloor A/B\rfloor$ and subtracting it from $Ax \equiv C \pmod{m}$, we have:

$(A-B\cdot \lfloor A/B\rfloor) x \equiv (C-D \cdot \lfloor A/B\rfloor) \pmod{m}$

In other words, $B'x \equiv D' \pmod{m}$, concluding the proof.

Exercise 48

Prove that INVERSE can be implemented in $O(n^3)$ time, when $a$ and $m$ are $n$-digit numbers.