Inverses modulo $n$

students, imagine trying to “undo” multiplication, but only using the numbers on a circular clock 🕒. In ordinary arithmetic, the inverse of $5$ is $\frac{1}{5}$ because $5\cdot \frac{1}{5}=1$. In modular arithmetic, we ask a similar question: which number can you multiply by to get $1$ again, but now taken modulo $n$?

What is a modular inverse?

For a number $a$, a modular inverse modulo $n$ is a number $x$ such that

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

If such an $x$ exists, we say that $a$ has an inverse modulo $n$, and we often write it as $a^{-1} \pmod n$.

This idea matters because it lets us solve equations like

$$ax \equiv b \pmod n$$

by “dividing” both sides by $a$ when an inverse exists. In modular arithmetic, division is not automatic. Instead, multiplication by the inverse plays the role of division.

Example

Find the inverse of $3$ modulo $7$.

We want a number $x$ such that

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

Check small values:

$3\cdot 1 = 3 \not\equiv 1 \pmod 7$
$3\cdot 2 = 6 \not\equiv 1 \pmod 7$
$3\cdot 3 = 9 \equiv 2 \pmod 7$
$3\cdot 5 = 15 \equiv 1 \pmod 7$

So $3^{-1} \equiv 5 \pmod 7$.

That means $3\cdot 5 \equiv 1 \pmod 7$ ✅

When does an inverse exist?

Not every number has an inverse modulo $n$. The key fact is:

$$a \text{ has an inverse modulo } n \iff \gcd(a,n)=1.$$

This means $a$ and $n$ must be coprime, which means they share no common factor greater than $1$.

Why does this matter? If $a$ and $n$ share a factor, then $ax$ can never be congruent to $1$ modulo $n$ because every multiple of $a$ will also carry that shared factor in its structure.

Example where an inverse exists

Does $4$ have an inverse modulo $9$?

Compute

$$\gcd(4,9)=1.$$

So yes, an inverse exists. Try numbers until you find one:

$$4\cdot 7=28 \equiv 1 \pmod 9$$

because $28=27+1$.

$$4^{-1} \equiv 7 \pmod 9.$$

Example where an inverse does not exist

Does $6$ have an inverse modulo $15$?

Compute

$$\gcd(6,15)=3.$$

Since the gcd is not $1$, there is no inverse modulo $15$.

That means there is no number $x$ such that

$$6x \equiv 1 \pmod {15}.$$

Why the gcd condition works

The condition $\gcd(a,n)=1$ is not just a rule to memorize. It comes from a deep result called Bézout’s identity.

Bézout’s identity says that if $\gcd(a,n)=1$, then there exist integers $s$ and $t$ such that

$$as+nt=1.$$

Now reduce both sides modulo $n$. Since $nt \equiv 0 \pmod n$, we get

$$as \equiv 1 \pmod n.$$

This shows that $s$ is an inverse of $a$ modulo $n$.

So the inverse is connected to a linear congruence of the form

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

That is exactly why inverses are part of the topic Linear Congruences.

Example using Bézout’s identity

Find the inverse of $7$ modulo $26$.

We need to solve

$$7x \equiv 1 \pmod {26}.$$

Use the Euclidean algorithm:

$$26=3\cdot 7+5$$

$$7=1\cdot 5+2$$

$$5=2\cdot 2+1$$

Now work backward:

$$1=5-2\cdot 2$$

$$2=7-1\cdot 5$$

$$5=26-3\cdot 7$$

Substitute step by step:

$$1=5-2(7-1\cdot 5)=3\cdot 5-2\cdot 7$$

and then

$$1=3(26-3\cdot 7)-2\cdot 7=3\cdot 26-11\cdot 7.$$

$$-11\cdot 7 \equiv 1 \pmod {26}.$$

Therefore

$$7^{-1} \equiv -11 \equiv 15 \pmod {26}.$$

Check:

$$7\cdot 15=105 \equiv 1 \pmod {26}.$$

Great! 🎉

How inverses help solve linear congruences

A linear congruence looks like

$$ax \equiv b \pmod n.$$

If $\gcd(a,n)=1$, then $a$ has an inverse modulo $n$. Multiply both sides by $a^{-1}$:

$$a^{-1}ax \equiv a^{-1}b \pmod n,$$

$$x \equiv a^{-1}b \pmod n.$$

This is the modular version of dividing by $a$.

Example

Solve

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

Since $3^{-1} \equiv 5 \pmod 7$, multiply both sides by $5$:

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

So the solution is

$$x \equiv 6 \pmod 7.$$

Check it:

$$3\cdot 6=18 \equiv 4 \pmod 7.$$

Correct ✅

Example with a trickier number

Solve

$$11x \equiv 7 \pmod {20}.$$

First check the gcd:

$$\gcd(11,20)=1.$$

So an inverse exists. Since

$$11\cdot 11=121 \equiv 1 \pmod {20},$$

we have

$$11^{-1} \equiv 11 \pmod {20}.$$

Multiply both sides by $11$:

$$x \equiv 11\cdot 7 \equiv 77 \equiv 17 \pmod {20}.$$

$$x \equiv 17 \pmod {20}.$$

Reduced residue systems and inverses

A reduced residue system modulo $n$ is the set of numbers from $1$ to $n-1$ that are coprime to $n$, with no repeats modulo $n$.

These are exactly the invertible numbers modulo $n$.

For example, modulo $10$, the numbers coprime to $10$ are

$$1,3,7,9.$$

So a reduced residue system modulo $10$ is

$$\{1,3,7,9\}.$$

Each of these has an inverse modulo $10$:

$1^{-1} \equiv 1 \pmod {10}$
$3^{-1} \equiv 7 \pmod {10}$ because $3\cdot 7=21 \equiv 1 \pmod {10}$
$7^{-1} \equiv 3 \pmod {10}$
$9^{-1} \equiv 9 \pmod {10}$ because $9\cdot 9=81 \equiv 1 \pmod {10}$

This shows an important pattern: in a reduced residue system, every number can be paired with its inverse, and some numbers may be their own inverse.

Why this is useful

Reduced residue systems help organize the numbers that can “act like units” modulo $n$. In other words, they describe exactly which numbers can be used for modular division.

They also connect to the idea that multiplying by a number coprime to $n$ rearranges the reduced residue system. For example, modulo $10$, multiplying each element of $\{1,3,7,9\}$ by $3$ gives another set of numbers that are still coprime to $10$.

Common mistakes to avoid

One common mistake is thinking every number has an inverse modulo $n$. That is false. Always check:

$$\gcd(a,n)=1.$$

Another mistake is trying to “cancel” numbers in a congruence without checking for an inverse. For example, from

$$6x \equiv 6 \pmod {15},$$

you cannot simply divide by $6$ because

$$\gcd(6,15)\ne 1.$$

In fact, this congruence has multiple solutions. Since $6x-6$ is divisible by $15$, we get

$$6(x-1)\equiv 0 \pmod {15}.$$

Checking values gives solutions like

$$x \equiv 1,6,11 \pmod {15}.$$

So cancellation only works when the number you want to cancel has an inverse modulo $n$.

Conclusion

Inverses modulo $n$ are the modular arithmetic version of division. A number $a$ has an inverse modulo $n$ exactly when $\gcd(a,n)=1$. This fact connects directly to linear congruences because solving

$$ax \equiv b \pmod n$$

becomes easy once $a^{-1}$ exists: multiply both sides by the inverse. Inverses also help explain reduced residue systems, which are the numbers that can be multiplied and still stay within the invertible set modulo $n$. students, mastering inverses modulo $n$ gives you a powerful tool for solving congruences, understanding modular structure, and working confidently in Number Theory 🚀

Study Notes

A modular inverse of $a$ modulo $n$ is a number $x$ such that $ax \equiv 1 \pmod n$.
An inverse exists if and only if $\gcd(a,n)=1$.
If $a^{-1}$ exists, then a linear congruence $ax \equiv b \pmod n$ can be solved by multiplying both sides by $a^{-1}$.
Bézout’s identity explains why inverses exist when $\gcd(a,n)=1$.
Reduced residue systems are the numbers modulo $n$ that are coprime to $n$; these are exactly the invertible numbers.
Not every number can be canceled in modular arithmetic. Cancellation works only when the number has an inverse modulo $n$.
Examples: $3^{-1} \equiv 5 \pmod 7$, $4^{-1} \equiv 7 \pmod 9$, and $7^{-1} \equiv 15 \pmod {26}$.