Modular Multiplicative Inverse

Definition

Suppose we are given a positive integer $m$. Consider the integers in modulo $m$ (i.e. all integers from $0$ to $m-1$). Then, for some integer $a$, we can find its modular multiplicative inverse, denoted by $a ^ {-1}$, which satisfy:

$a \cdot a^{-1} \equiv 1 \; (mod \, m)$

We should note that the modular inverse does not always exist. For example, let $m = 4$, $a = 2$. Obviously we cannot find $a^{-1}$ satisfying the above equation. It can be proven that the modular inverse exists if and only if $a$ and $m$ are relatively prime (i.e. $gcd(a, m) = 1$).

In this article, we present two methods for finding the modular inverse in case it exists, and one method for finding all the modular inverse of all numbers in linear time.

Finding the Modular Inverse using Extended Euclidean algorithm

Consider the following equation (with unknown $x$ and $y$):

$a \cdot x + m \cdot y = 1$

This is known as Linear Diophantine equation of two variables. As shown in the linked article, when $gcd(a, m) = 1$, the equation has a solution which can be found using the extended Euclidean algorithm. Note that $gcd(a, m) = 1$ is also the condition for the Modular inverse to exist.

Now, if we take modulo $m$ of both sides, we can get rid of $m \cdot y$, and the equation becomes:

$a \cdot x \equiv 1 \; (mod \, m)$

Thus, the modular inverse of $a$ is $x$.

The implementation is as follows:

int x, y;
int g = extended_euclidean(a, m, x, y);
if (g != 1) cout << "No solution!";
else {
    x = (x % m + m) % m;
    cout << x << endl;
}

Finding the Modular Inverse using Binary Exponentiation

Another method for finding modular inverse is to use Euler's theorem, which is as follows:

$a ^ {\phi (m)} \equiv 1 \; (mod \, m)$

which is true when $a$ and $m$ are relatively prime. (Again, note that this was also our condition for Modular inverse to exist).

If $m$ is a prime number, we have an even simpler equation from Fermat's little theorem:

$a ^ {m - 1} \equiv 1 \; (mod \, m)$

Multiply both sides of the above equations by $a ^ {-1}$, and we get:

From these results, we can easily find the modular inverse using binary exponentiation algorithm, which works in time $O(\log m)$.

Even though this method is easier to understand than the method described in previous paragraph, in the case when $m$ is not a prime number, we need to calculate Euler phi function, which involves factorization of $m$, which might be very hard. If the prime factorization of $m$ is known, then the complexity of this method is $O(\log m)$.

Finding all Modular Inverse of numbers in modulo $m$

In this section, we consider a special case when $m$ is a prime number, and we will describe a method that can calculate all the Modular inverse of every number in range $[1, m-1]$.

Applying the algorithms described in previous sections, we obtain a solution with complexity $O(m \log m)$. Here we present a better algorithm with complexity $O(m)$. The method is as follows: We denote by $r[i]$ the modular inverse of $i$. Then when $i > 1$, we have:

$r[i] = - \lfloor \frac{m}{i} \rfloor \cdot r[m \, mod \, i] \; (mod \, m)$

The implementation is very simple:

r[1] = 1;
for(int i = 2; i < m; ++i)
    r[i] = (m - (m/i) * r[m%i] % m) % m;

Proof

We have:

$m \, mod \, i = m - \lfloor \frac{m}{i} \rfloor \cdot i$

Then, taking both sides modulo $m$ yield:

$m \, mod \, i = - \lfloor \frac{m}{i} \rfloor \cdot i \; (mod \, m)$

Multiply both sides by modular inverse of $i$ and then by modular inverse of $(m \, mod \, i)$ yield:

$r[i] = - \lfloor \frac{m}{i} \rfloor \cdot r[m \, mod \, i] \; (mod \, m)$

Practice Problems