[Introduction to Number Theory Series Part 13] When Does a Modular Inverse Exist?

In ordinary arithmetic, dividing by 2 or 3 feels routine. In modular arithmetic, division is possible only when the number you want to divide by has an inverse.

What this post covers

• What a modular inverse is
• Why modular division is really inverse multiplication
• Why inverses exist exactly when two numbers are coprime
• How this helps solve linear congruences

Key terms

• modular inverse: a number that multiplies to 1 modulo n
• coprime: having gcd 1
• congruence: having the same remainder modulo n
• linear congruence: an equation of the form ax \equiv b \pmod n

What is a modular inverse?

For an integer a, an integer x is called an inverse of a modulo n if

$$ax \equiv 1 \pmod n.$$

If such an x exists, dividing by a in the modular world can be replaced by multiplying by x. Any other integer congruent to x modulo n represents the same inverse class.

Example: the inverse of 3 modulo 7

We want

$$3x \equiv 1 \pmod 7.$$

Testing small values shows

$$3\times 5 = 15 \equiv 1 \pmod 7.$$

So 5 is an inverse of 3 modulo 7. Equivalently, 12, 19, and any number congruent to 5 modulo 7 represent the same inverse.

The existence condition

The key theorem is:

a has an inverse modulo n if and only if gcd(a,n)=1.

So inverses exist exactly when a and n are coprime.

Why does the coprime condition matter?

If a and n have a common divisor d>1, then every product ax is divisible by d. But if

$$ax \equiv 1 \pmod n,$$

then ax-1 would have to be divisible by n, hence by d. That is impossible because ax is divisible by d while ax-1 is not.

Conversely, if gcd(a,n)=1, then Bézout's identity gives integers x and y such that

$$ax+ny=1.$$

Reducing modulo n gives

$$ax \equiv 1 \pmod n,$$

so x is an inverse.

Example: why 2 has no inverse modulo 6

Since

$$\gcd(2,6)=2,$$

2 and 6 are not coprime. Indeed, the products of 2 modulo 6 cycle through only 0,2,4, never 1.

Why is this useful?

Suppose we want to solve

$$3x \equiv 4 \pmod 7.$$

Since 5 is an inverse of 3 modulo 7, multiply both sides by 5:

$$x \equiv 5\cdot 4 = 20 \equiv 6 \pmod 7.$$

Common mistakes

1. Assuming every nonzero number has an inverse

That is true in a field, not in every modulus.

2. Forgetting to check gcd(a,n)=1

That is the main condition.

3. Thinking only one representative counts as the inverse

If 5 is an inverse modulo 7, then 12, 19, and any number congruent to 5 modulo 7 represent the same inverse class.

Wrap-up

A modular inverse exists exactly in the coprime case. That turns modular “division” into multiplication by an inverse.

Next we use this to solve linear congruences of the form ax \equiv b \pmod n.