Modular Multiplicative Inverse using Fermat's Little Theorem

In our previous lesson, we built an efficient tool for calculating huge powers under a modulus: binary exponentiation. You learned how to compute $a^{b} (mod m)$ in $O (lo g b)$ time, a crucial skill for competitive programming. With modular addition, subtraction, multiplication, and exponentiation now in your arsenal, one fundamental arithmetic operation remains: division.

This lesson tackles that final piece of the puzzle. We will explore how to perform division in modular arithmetic, such as calculating $(a / b) (mod m)$ . You'll discover that this isn't as simple as (a \pmod m) / (b \pmod m). Instead, it requires finding a special number called the modular multiplicative inverse. We will define this concept and then use a beautiful and powerful result from number theory, Fermat's Little Theorem, to compute it efficiently when the modulus is a prime number.

By the end of this lesson, you will be able to perform all four basic arithmetic operations in a modular context, a complete toolkit for a wide range of number theory problems.

The Problem with Division and the Idea of an Inverse

In the world of real numbers, dividing by $b$ is the same as multiplying by its reciprocal, $1/ b$ . For example, $10 \div 2 = 10 \times 0.5 = 5$ . The number $0.5$ is the multiplicative inverse of $2$ because $2 \times 0.5 = 1$ . We can apply this same idea to modular arithmetic.

To compute $(a / b) (mod m)$ , we redefine the problem as $(a \cdot b^{- 1}) (mod m)$ , where $b^{- 1}$ is the modular multiplicative inverse of $b$ . This is an integer $x$ such that $b \cdot x \equiv 1 (mod m)$ . Once we find this integer $x$ , division becomes a simple multiplication.

The following reading formally defines the modular multiplicative inverse and states the condition under which it exists.

Modular Inverse - Algorithms for Competitive Programming

This article from CP-Algorithms provides a concise definition of the modular multiplicative inverse.

Read the section Definition. Pay close attention to the formal definition and the critical condition for an inverse to exist: gcd(a, m) = 1.

As you just read, the inverse of a modulo m exists only if a and m are relatively prime. This is a crucial fact to remember. For the scope of this lesson, we will focus on a very common case in competitive programming: when the modulus m is a prime number. If m is prime and a is not a multiple of m, then gcd(a, m) is always 1, so the inverse is guaranteed to exist.

So, how do we find this inverse? We'll use a famous theorem.

Fermat's Little Theorem

Fermat's Little Theorem provides a direct and elegant way to find the modular inverse when the modulus is prime. The theorem itself is a cornerstone of number theory.

Fermat's Little Theorem states: If $p$ is a prime number, then for any integer $a$ not divisible by $p$ , we have:
$a^{p - 1} \equiv 1 (mod p)$

To build a strong intuition for this theorem, the following video provides some excellent examples and a visual walkthrough of the proof.

Fermat's Little Theorem ← Number Theory

The video "Fermat's Little Theorem" from the Socratica channel offers a clear and accessible introduction to the theorem and its proof.

First, watch the introduction from the beginning to the examples to see the theorem in action. Afterwards, to understand why it works, watch the proof walkthrough. The proof itself is beautiful and enhances understanding, even if you don't need to reproduce it in a contest.

From Theorem to Inverse

The connection between Fermat's Little Theorem and the modular inverse is remarkably simple. We start with the theorem's statement:
$a^{p - 1} \equiv 1 (mod p)$

We can rewrite the left side:
$a \cdot a^{p - 2} \equiv 1 (mod p)$

Now, compare this with the definition of the modular inverse, $a \cdot a^{- 1} \equiv 1 (mod p)$ . By matching the two equations, we get a formula for the inverse:
$a^{- 1} \equiv a^{p - 2} (mod p)$

This is our main result! To find the modular inverse of $a$ modulo a prime $p$ , we simply need to calculate $a^{p - 2} (mod p)$ . And how do we calculate this power efficiently? Using the binary exponentiation algorithm you mastered in the last lesson.

The following resources confirm this derivation and set the stage for implementation.

Modular Inverse - Algorithms for Competitive Programming

This section of the CP-Algorithms article shows the derivation we just discussed.

Read the section Finding the Modular Inverse using Binary Exponentiation. This directly connects Euler's and Fermat's theorems to the modular inverse formula.

The next video, from competitive programming expert Errichto, summarizes this exact technique in the context of a contest problem.

Computations Modulo P in Competitive Programming

In this segment of his video on modular computations, Errichto quickly explains how division is handled using the inverse and states the p-2 power formula.

Watch the short clip from defining the inverse to see how a top competitor views this problem. He calls the formula "magic," which highlights its power and utility.

Implementation in C++

Now we have all the pieces. To find $(a / b) (mod p)$ :

Check that $p$ is prime and $b$ is not a multiple of $p$ .
Calculate the modular inverse of $b$ , which is $b^{p - 2} (mod p)$ , using your binary exponentiation function.
The final result is $(a \cdot b^{- 1}) (mod p)$ .

The article from GeeksforGeeks provides a complete, self-contained C++ implementation that you can adapt for your needs. It includes the power function (for binary exponentiation) and a modInverse function that uses it.

Fermat's little theorem

This GeeksforGeeks article demonstrates the use of Fermat's Little Theorem for finding the modular inverse and provides a full C++ implementation.

First, read the section Use of Fermat's little theorem to see the derivation of the inverse formula one more time. Then, study the C++ implementation. Notice how it relies on a power function—exactly the one we studied last time.

Here is a clean version of the necessary functions for your C++ template.

// Computes (base^exp) % mod
long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

// Computes the modular inverse of n modulo mod
long long modInverse(long long n, long long mod) {
    // Uses Fermat's Little Theorem: n^(mod-2) % mod
    return power(n, mod - 2, mod);
}

// Example of modular division
// To compute (a/b) % mod:
// long long result = (a * modInverse(b, mod)) % mod;

A Walkthrough Example

Let's compute $(5/3) (mod 13)$ by hand to solidify the process.

Problem: We need to find $(5 \cdot 3^{- 1}) (mod 13)$ .
Find the inverse: The modulus is a prime, 13. We need to find $3^{- 1} (mod 13)$ . Using Fermat's Little Theorem, this is $3^{13 - 2} (mod 13)$ , which simplifies to $3^{11} (mod 13)$ .
Use Binary Exponentiation: Let's calculate $3^{11} (mod 13)$ . The binary representation of 11 is 1011.
- 3^1 ≡ 3 \pmod{13}
- 3^2 ≡ 9 \pmod{13}
- 3^4 ≡ 9^2 = 81 ≡ (6 \cdot 13 + 3) \equiv 3 \pmod{13}
- 3^8 ≡ 3^2 = 9 \pmod{13}
- Since $11 = 8 + 2 + 1$ , we multiply the corresponding powers:
  $3^{11} = 3^{8} \cdot 3^{2} \cdot 3^{1} \equiv 9 \cdot 9 \cdot 3 (mod 13)$
  $\equiv 81 \cdot 3 (mod 13)$
  $\equiv 3 \cdot 3 = 9 (mod 13)$
- So, the inverse of 3 modulo 13 is 9. (Check: $3 \cdot 9 = 27 = 2 \cdot 13 + 1 \equiv 1 (mod 13)$ . Correct.)
Final Calculation: Now we substitute the inverse back into the original problem:
$(5 \cdot 3^{- 1}) (mod 13) \equiv (5 \cdot 9) (mod 13)$
$\equiv 45 (mod 13)$
$\equiv (3 \cdot 13 + 6) \equiv 6 (mod 13)$
The answer is 6.

Conclusion

Today, you have completed your understanding of basic modular arithmetic. You've bridged the gap from multiplication to division by mastering the concept of the modular multiplicative inverse.

Here are the key takeaways:

Modular division $(a / b) (mod m)$ is performed by multiplying with the modular inverse: $(a \cdot b^{- 1}) (mod m)$ .
The modular inverse of $b$ modulo $m$ , denoted $b^{- 1}$ , is an integer $x$ such that $b \cdot x \equiv 1 (mod m)$ . It exists only if $g cd (b, m) = 1$ .
Fermat's Little Theorem provides a powerful shortcut when the modulus $m$ is a prime number $p$ : $b^{- 1} \equiv b^{p - 2} (mod p)$ .
This calculation is made efficient by using the binary exponentiation algorithm, giving a total time complexity of $O (lo g p)$ to find the inverse.

You now have a robust method for handling division in problems with a prime modulus. But what happens if the modulus is not prime? In that case, Fermat's Little Theorem does not apply. Our next lesson will introduce a more general tool, the Extended Euclidean Algorithm, which can find the modular inverse for any modulus, prime or composite, as long as the existence condition is met. This will also allow us to solve another class of problems: linear congruences.