Modular Inverses

Division in Modular Arithmetic

In ordinary arithmetic, division by a nonzero number means multiplication by its reciprocal. Modular arithmetic is more delicate. A residue class may or may not have a multiplicative inverse.

Let $a$ and $n$ be integers with $n\ge2$. A modular inverse of $a$ modulo $n$ is an integer $b$ satisfying

When such a $b$ exists, we write

This means that multiplication by $a$ can be undone modulo $n$.

Existence Criterion

An integer $a$ has a multiplicative inverse modulo $n$ if and only if

Indeed, the congruence

means that

for some integer $y$. Equivalently,

Thus $1$ is an integer linear combination of $a$ and $n$. By Bezout’s criterion, this happens exactly when

So invertibility modulo $n$ is exactly the same as coprimality with $n$.

Example

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

Since

an inverse exists.

Use the Euclidean algorithm:

Now work backward:

Since

we get

Since

we obtain

Thus

Therefore

Indeed,

Uniqueness of Inverses

If an inverse exists, it is unique modulo $n$.

Suppose

and

Then

Since $\gcd(a,n)=1$, cancellation is valid modulo $n$, so

Thus all inverses of $a$ modulo $n$ lie in one residue class.

Units Modulo $n$

A residue class $[a]_n$ is called a unit if it has a multiplicative inverse in $\mathbb{Z}/n\mathbb{Z}$.

The set of all units modulo $n$ is denoted by

It consists exactly of the classes

such that

For example, modulo $10$, the units are

The classes $[2]_{10}$, $[4]_{10}$, $[5]_{10}$, $[6]_{10}$, and $[8]_{10}$ are not units because each has a common divisor greater than $1$ with $10$.

Prime Moduli

If $p$ is prime, then every nonzero residue class modulo $p$ is invertible.

Indeed, if

then $p\nmid a$, so

Therefore $[a]_p$ has an inverse.

Thus

is a field. This means that addition, subtraction, multiplication, and division by nonzero classes are all possible.

For example, modulo $7$,

because

Composite Moduli

If $n$ is composite, not every nonzero class modulo $n$ is invertible.

For example, modulo $12$, the class $[5]_{12}$ is a unit because

Its inverse is itself:

But $[4]_{12}$ is not a unit because

There is no integer $b$ such that

The obstruction is common divisibility.

Solving Congruences by Inverses

When

the linear congruence

can be solved by multiplying both sides by $a^{-1}$:

For example, solve

Since

we have

Therefore

Inverses and the Extended Euclidean Algorithm

The extended Euclidean algorithm is the standard method for finding modular inverses.

To find $a^{-1}\pmod n$, compute integers $x$ and $y$ such that

If

then

Reducing modulo $n$, we obtain

Hence

This gives an efficient and constructive procedure.

Role in Number Theory

Modular inverses make division possible in modular arithmetic, but only for classes coprime to the modulus.

They are essential in solving linear congruences, proving Euler’s theorem, constructing the Chinese remainder theorem, and building cryptographic systems.

The main principle is that modular division is not governed by whether $a\ne0$, but by whether

Coprimality replaces nonzero-ness as the correct condition for invertibility modulo $n$.