Course contentsShow
← Mathematics
Lesson 2735 of 3,12154. Number TheoryFree lesson

Division and Modular Inverses

Understand when division is valid in modular arithmetic through multiplicative inverses when gcd(a,n) = 1.

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.