# 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

$$
ab\equiv1\pmod n.
$$

When such a $b$ exists, we write

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

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

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

Indeed, the congruence

$$
ab\equiv1\pmod n
$$

means that

$$
ab-1=ny
$$

for some integer $y$. Equivalently,

$$
ab-ny=1.
$$

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

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

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

## Example

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

Since

$$
\gcd(7,26)=1,
$$

an inverse exists.

Use the Euclidean algorithm:

$$
26=7\cdot3+5,
$$

$$
7=5\cdot1+2,
$$

$$
5=2\cdot2+1.
$$

Now work backward:

$$
1=5-2\cdot2.
$$

Since

$$
2=7-5,
$$

we get

$$
1=5-2(7-5)=3\cdot5-2\cdot7.
$$

Since

$$
5=26-3\cdot7,
$$

we obtain

$$
1=3(26-3\cdot7)-2\cdot7
=3\cdot26-11\cdot7.
$$

Thus

$$
-11\cdot7\equiv1\pmod{26}.
$$

Therefore

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

Indeed,

$$
7\cdot15=105\equiv1\pmod{26}.
$$

## Uniqueness of Inverses

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

Suppose

$$
ab\equiv1\pmod n
$$

and

$$
ac\equiv1\pmod n.
$$

Then

$$
ab\equiv ac\pmod n.
$$

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

$$
b\equiv c\pmod n.
$$

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

$$
(\mathbb{Z}/n\mathbb{Z})^\times.
$$

It consists exactly of the classes

$$
[a]_n
$$

such that

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

For example, modulo $10$, the units are

$$
[1]_{10},[3]_{10},[7]_{10},[9]_{10}.
$$

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

$$
1\le a\le p-1,
$$

then $p\nmid a$, so

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

Therefore $[a]_p$ has an inverse.

Thus

$$
\mathbb{Z}/p\mathbb{Z}
$$

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

For example, modulo $7$,

$$
3^{-1}\equiv5\pmod7,
$$

because

$$
3\cdot5=15\equiv1\pmod7.
$$

## 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

$$
\gcd(5,12)=1.
$$

Its inverse is itself:

$$
5\cdot5=25\equiv1\pmod{12}.
$$

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

$$
\gcd(4,12)=4.
$$

There is no integer $b$ such that

$$
4b\equiv1\pmod{12}.
$$

The obstruction is common divisibility.

## Solving Congruences by Inverses

When

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

the linear congruence

$$
ax\equiv b\pmod n
$$

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

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

For example, solve

$$
4x\equiv3\pmod{11}.
$$

Since

$$
4\cdot3=12\equiv1\pmod{11},
$$

we have

$$
4^{-1}\equiv3\pmod{11}.
$$

Therefore

$$
x\equiv3\cdot3=9\pmod{11}.
$$

## 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

$$
ax+ny=\gcd(a,n).
$$

If

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

then

$$
ax+ny=1.
$$

Reducing modulo $n$, we obtain

$$
ax\equiv1\pmod n.
$$

Hence

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

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

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

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