Modular Inverse

The problem with division

You've seen how addition, subtraction, and multiplication work smoothly in modular arithmetic. We can take the modulus at each step to keep numbers manageable. Division, however, is a different story. The straightforward approach doesn't work.

For example, $(10 / 2) \pmod 4$ is $5 \pmod 4$ , which is $1$ . But if we try to take the modulus first, we get $(10 \pmod 4) / (2 \pmod 4)$ , which is $2 / 2 = 1$ . This case seems to work.

Let's try another: $(20 / 5) \pmod 3$ is $4 \pmod 3$ , which is $1$ . But $(20 \pmod 3) / (5 \pmod 3)$ is $2 / 2 = 1$ . So far so good.

What about $(15 / 3) \pmod 4$ ? That's $5 \pmod 4$ , which is $1$ . But $(15 \pmod 4) / (3 \pmod 4)$ is $3 / 3 = 1$ . Still seems to work.

Okay, let's try this one: $(10 / 5) \pmod 3$ . That's $2 \pmod 3$ , which is $2$ . But $(10 \pmod 3) / (5 \pmod 3)$ is $1 / 2$ . Now we have a problem. What is $1/2$ in the world of integers and remainders?

In regular arithmetic, dividing by a number is the same as multiplying by its reciprocal. For instance, dividing by 5 is the same as multiplying by $5^{-1}$ , or $1/5$ . We need an equivalent concept for modular arithmetic.

Modular multiplicative inverse

The modular equivalent of a reciprocal is called the modular multiplicative inverse. The inverse of a number $a$ modulo $m$ is a number $x$ such that their product is congruent to 1.

a \cdot x \equiv 1 \pmod m

With this inverse, we can redefine division. To compute $(b / a) \pmod m$ , we instead calculate $(b \cdot a^{-1}) \pmod m$ .

This raises a critical question: does an inverse always exist?

In short, no. A modular inverse $a^{-1} \pmod m$ exists only if $a$ and $m$ are coprime. That is, their greatest common divisor must be 1.

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$ ).

For example, the inverse of $3 \pmod 7$ exists because $\gcd(3, 7) = 1$ . We are looking for a number $x$ where $3x \equiv 1 \pmod 7$ . If we test values, we find that $x=5$ works, because $3 \cdot 5 = 15$ , and $15 \equiv 1 \pmod 7$ . So, $3^{-1} \equiv 5 \pmod 7$ .

Conversely, the inverse of $2 \pmod 4$ does not exist because $\gcd(2, 4) = 2$ . No matter which integer $x$ you multiply by 2, the result modulo 4 will always be an even number ( $0$ or $2$ ), never $1$ .

Finding the inverse by trial and error is slow. We need a more systematic and efficient method, especially for large numbers.

Using the Extended Euclidean Algorithm

The Extended Euclidean Algorithm is a powerful tool that not only finds the greatest common divisor of two integers $a$ and $m$ , but also finds two other integers, $x$ and $y$ , that satisfy Bézout's identity.

ax + my = \gcd(a, m)

How does this help us find the modular inverse? If we know that $a$ and $m$ are coprime, then their gcd is 1. The equation becomes:

ax + my = 1

Now, let's take this equation modulo $m$ . The term $my$ becomes $0$ , because any multiple of $m$ is congruent to $0 \pmod m$ . This simplifies the equation dramatically.

ax \equiv 1 \pmod m

The algorithm works recursively. The base case for the recursion is when $a=0$ , where $\gcd(0, m) = m$ . In this case, $x=0$ and $y=1$ . For the recursive step, we use the results from a smaller problem, extendedGcd(m % a, a), to build the solution for extendedGcd(a, m).

Here is a C++ implementation. It returns the gcd and finds the values for $x$ and $y$ , which are passed by reference.

// C++ function for Extended Euclidean Algorithm
// It returns gcd(a, b) and finds the values of x and y such that
// ax + by = gcd(a, b)
int extendedGcd(int a, int b, int &x, int &y) {
    // Base Case
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }

    int x1, y1; // To store results of recursive call
    int gcd = extendedGcd(b % a, a, x1, y1);

    // Update x and y using results of recursive call
    x = y1 - (b / a) * x1;
    y = x1;

    return gcd;
}

Putting it all together

Now we can write a function to calculate the modular inverse. This function will use our extendedGcd implementation. Remember, we must first check that an inverse actually exists.

#include <iostream>

// Extended Euclidean Algorithm function from before
int extendedGcd(int a, int b, int &x, int &y) { /* ... */ }

// Function to find modular inverse of a under modulo m
void modInverse(int a, int m) {
    int x, y;
    int g = extendedGcd(a, m, x, y);
    if (g != 1) {
        std::cout << "Inverse doesn't exist";
    } else {
        // The value of x can be negative, so we adjust it
        int result = (x % m + m) % m;
        std::cout << "Modular multiplicative inverse is " << result;
    }
}

int main() {
    int a = 3, m = 7;
    modInverse(a, m); // Output: Modular multiplicative inverse is 5
    return 0;
}

Notice the line (x % m + m) % m. The Extended Euclidean Algorithm can return a negative value for $x$ . Since we want a positive result in the range $[0, m-1]$ , we add $m$ to bring it into the positive range before taking the modulus one last time. This is a standard trick for handling potential negative results in modular arithmetic.

With this function, we can now perform modular division. To calculate $(b / a) \pmod m$ , you would first call modInverse(a, m) to get $a^{-1}$ , and then compute $(b \cdot a^{-1}) \pmod m$ using the modular multiplication techniques you've already learned. This is a fundamental operation in many algorithms used in competitive programming, particularly in combinatorics and number theory problems.

Quiz Questions 1/6

Why is direct division, such as calculating $(10 \pmod 3) / (5 \pmod 3)$ , problematic in modular arithmetic?

Quiz Questions 2/6

The modular multiplicative inverse of a number $a$ modulo $m$ is a number $x$ such that:

Mastering Modular Arithmetic for Algorithms