Division and Modular Inverses
What You'll Learn
You'll discover when and how division works in modular arithmetic by understanding multiplicative inverses.
The Problem with Division
In ordinary arithmetic, dividing by a means multiplying by 1/a. But in modular arithmetic, we don't have fractions! So how do we "divide" by a number modulo n?
The answer: we use modular inverses.
Multiplicative Inverses Modulo n
A number a has a multiplicative inverse modulo n if there exists a number b such that:
a · b ≡ 1 (mod n)
We call b the inverse of a, often written as a⁻¹.
Example: Consider a = 3 and n = 7.
We need 3 · b ≡ 1 (mod 7).
Testing: 3 · 5 = 15 ≡ 1 (mod 7).
So 3⁻¹ ≡ 5 (mod 7).
Now "dividing by 3" modulo 7 means "multiplying by 5":
6 ÷ 3 ≡ 6 · 5 ≡ 30 ≡ 2 (mod 7). ✓
When Does an Inverse Exist?
Critical condition: a has a multiplicative inverse modulo n if and only if gcd(a, n) = 1 (they're relatively prime).
Why? If gcd(a, n) = 1, Bézout's Identity guarantees integers x, y such that ax + ny = 1. Taking this modulo n, we get ax ≡ 1 (mod n), so x is the inverse!
Non-example: Can 4 have an inverse modulo 6?
gcd(4, 6) = 2 ≠ 1, so no inverse exists. Division by 4 modulo 6 is undefined.
Finding the Inverse
Use the Extended Euclidean Algorithm to find x in ax + ny = 1; then x (mod n) is your inverse.
Key Takeaway: Division by a modulo n is valid (via multiplication by a⁻¹) only when gcd(a, n) = 1.