Modular Division Using Modular Inverse

Welcome back! In our last lesson, you mastered a key technique in competitive programming: finding the modular multiplicative inverse for a prime modulus using Fermat's Little Theorem. You learned that for a prime $p$ , the inverse of $a$ is simply $a^{p - 2} (mod p)$ , and you know how to compute this efficiently with binary exponentiation.

Today, we will put that knowledge to work. This lesson connects the concept of an inverse to its primary purpose: performing modular division. You will learn how to compute expressions like $(a / b) (mod p)$ , a task that frequently appears in competitive programming problems but cannot be done with simple division. By transforming division into multiplication, you will complete your toolkit for all four basic arithmetic operations in the world of modular arithmetic.

Division Through Multiplication

The core idea is simple and elegant. In standard arithmetic, dividing by a number $b$ is the same as multiplying by its reciprocal, $b^{- 1}$ . We apply the exact same logic in modular arithmetic. The expression $(a / b) (mod p)$ is not computed directly. Instead, we calculate it as:
$(a \cdot b^{- 1}) (mod p)$
where $b^{- 1}$ is the modular multiplicative inverse of $b$ modulo $p$ .

Since you already know how to find $b^{- 1}$ when $p$ is prime, the process becomes straightforward. The following reading from a Codeforces blog post, written specifically for competitive programmers, formalizes this exact step.

Modular Arithmetic for Beginners

This blog post on Codeforces is an excellent resource for understanding modular arithmetic from a practical, problem-solving perspective. This particular section defines modular division.

Please read the two short paragraphs under the second pow_mod function. Focus on the final formula presented for the division operator. This is the central concept for this entire lesson.

As the text confirms, modular division is simply multiplication by the modular inverse. This elegantly sidesteps the ambiguity of what "division" means in a system of integer remainders.

The Complete Algorithm

Let's combine everything you've learned into a single, step-by-step procedure for calculating $(a / b) (mod p)$ , where $p$ is a prime number.

Find the Inverse of the Divisor: The first step is to find the modular multiplicative inverse of the denominator, $b$ . Using Fermat's Little Theorem, we know this is $b^{p - 2} (mod p)$ .
Calculate the Inverse: Use the binary exponentiation algorithm (which you've named power in your C++ template) to compute power(b, p - 2, p).
Perform Multiplication: Multiply the numerator, $a$ , by the inverse you just found, and take the result modulo $p$ . The final expression is (a * power(b, p - 2, p)) % p.

Implementation in C++

Here is how you can implement a modDivide function in C++. It relies on the power function from our lesson on binary exponentiation and the modInverse function from our last lesson.

// A prime modulus, e.g., 10^9 + 7
const int MOD = 1e9 + 7;

// Computes (base^exp) % mod in O(log exp)
long long power(long long base, long long exp) {
    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 using Fermat's Little Theorem
long long modInverse(long long n) {
    return power(n, MOD - 2);
}

// Computes (a / b) % MOD
long long modDivide(long long a, long long b) {
    a %= MOD;
    long long inv_b = modInverse(b);
    return (a * inv_b) % MOD;
}

// Example usage:
// long long result = modDivide(100, 5); // Computes (100 / 5) % MOD

Note: This code assumes a fixed prime modulus MOD. In a contest, you might pass the modulus p as a parameter to these functions if it changes between problems. Also, remember to handle the intermediate multiplication with long long to prevent overflow, as in (res * base).

A Worked Example

Let's trace the algorithm with a concrete example. Suppose we need to calculate $(50/4) (mod 13)$ .

Here, $a = 50$ , $b = 4$ , and $p = 13$ .

Find the inverse of $b$ : We need to find $4^{- 1} (mod 13)$ .
Calculate using Fermat's Little Theorem: The inverse is $4^{13 - 2} (mod 13) = 4^{11} (mod 13)$ .
- We use binary exponentiation to find $4^{11} (mod 13)$ .
- $11$ in binary is 1011.
- $4^{1} \equiv 4 (mod 13)$
- $4^{2} \equiv 16 \equiv 3 (mod 13)$
- $4^{4} \equiv 3^{2} \equiv 9 (mod 13)$
- $4^{8} \equiv 9^{2} \equiv 81 \equiv 81 - 6 \cdot 13 = 81 - 78 = 3 (mod 13)$
- $4^{11} = 4^{8} \cdot 4^{2} \cdot 4^{1} \equiv 3 \cdot 3 \cdot 4 (mod 13)$
- $\equiv 9 \cdot 4 = 36 (mod 13)$
- $36 = 2 \cdot 13 + 10$ , so $36 \equiv 10 (mod 13)$ .
- Thus, $4^{- 1} \equiv 10 (mod 13)$ . (Let's check: $4 \cdot 10 = 40 = 3 \cdot 13 + 1 \equiv 1 (mod 13)$ . It's correct!)
Perform the final multiplication:
$(50/4) (mod 13) \equiv (50 \cdot 10) (mod 13)$
First, reduce $50 (mod 13)$ : $50 = 3 \cdot 13 + 11$ , so $50 \equiv 11 (mod 13)$ .
$\equiv (11 \cdot 10) (mod 13)$
$\equiv 110 (mod 13)$
To find $110 (mod 13)$ , we can divide: $110 = 8 \cdot 13 + 6 = 104 + 6$ .
$\equiv 6 (mod 13)$
The final answer is 6. This means 6 is the number that, when multiplied by 4, gives 50 in modulo 13 arithmetic: $4 \cdot 6 = 24$ , and $24 \equiv 11 (mod 13)$ , which is the same as $50 (mod 13)$ . Our calculation is correct.

Application: A Glimpse into Combinatorics

Why is this so important in competitive programming? Many problems, especially in combinatorics, involve formulas with division. A classic example is the binomial coefficient "n choose k":
$(k n) = \frac{n !}{k ! ( n - k )!}$
When a problem asks you to compute this value modulo a prime $p$ , you cannot simply compute the huge factorials and then divide. Instead, you compute the factorials modulo $p$ and then use modular division. The formula becomes:
$(k n) (mod p) \equiv (n! \cdot (k!)^{- 1} \cdot ((n - k)!)^{- 1}) (mod p)$
This is a powerful application that we will explore in depth in a future module. The Codeforces article you read from earlier briefly touches upon this.

Modular Arithmetic for Beginners

This last reading gives a quick preview of why modular division is so essential.

In the same blog post, look at the paragraph that starts with You can also now take advantage. This shows the direct application of modular division to a common combinatorial formula, highlighting its practical importance.

Conclusion

You have now completed the quartet of modular arithmetic operations. By understanding that division is just multiplication by an inverse, you can solve a much broader class of problems.

Let's summarize today's key points:

Modular division $(a / b) (mod p)$ is defined as multiplication by the modular inverse: $(a \cdot b^{- 1}) (mod p)$ .
For a prime modulus $p$ , the inverse $b^{- 1}$ is calculated as $b^{p - 2} (mod p)$ , using the binary exponentiation algorithm for efficiency.
The entire operation can be wrapped in a single function, modDivide(a, b), which calls your modInverse function.
This technique is fundamental for solving many combinatorics problems in a modular context.

In our next lesson, we will solve a slightly different but related problem: linear congruences. We will learn how to find solutions for $x$ in equations of the form $a x \equiv b (mod m)$ . You will see that finding $(b / a) (mod m)$ is actually a special case of solving this equation.