Modular Inverses

Suppose you want to solve $7x \equiv 1 \pmod{31}$ . Is there an integer $x$ that plays the role of " $1/7$ "? This is true in the world of remainders modulo 31. This is the question of modular inverses. It turns out to have a remarkably clean answer. Division is the one arithmetic operation that fails to survive intact. This happens when we pass from ordinary integers to residues modulo $n$ . Understanding exactly when it survives — and how to recover it — is one of the foundational pillars on which the rest of elementary number theory is built. The idea matters because so much of number theory, cryptography, and computer algebra is secretly about solving equations inside $\mathbb{Z}/n\mathbb{Z}$ . Every time RSA encryption decrypts a message, the same question lurks underneath. Every time a computer algebra system solves a linear congruence, it lurks too. Every time a hash table probes indices modulo its size, the question reappears. For which $a$ does there exist a multiplicative partner $b$ with $ab \equiv 1$ ? And how do we find it fast? The answer — exactly when $\gcd(a,n)=1$ — is short to state. But it is rich in consequence. It connects Bezout's Identity, The Extended Euclidean Algorithm, and the structure of $(\mathbb{Z}/n\mathbb{Z})^{\times}$ as a group. The big picture is that modular arithmetic modulo $n$ forms a ring. The units of that ring have multiplicative inverses. These units form a group under multiplication. Classifying the units of $\mathbb{Z}/n\mathbb{Z}$ is the first step toward Euler's theorem. It also leads toward Fermat's little theorem, and the notion of the Order of an Element. Eventually it connects to the structure theory of finite abelian groups applied to number theory. Without inverses we cannot even meaningfully "divide" in modular arithmetic. So solving Linear Congruences of the form $ax \equiv b \pmod n$ reduces almost entirely to first finding an inverse of $a$ . This article gives the precise definition of a modular inverse. It proves the fundamental existence theorem: invertibility holds exactly when $\gcd(a,n)=1$ . It gives a full algorithmic account of how to compute inverses via the extended Euclidean algorithm. It works two nontrivial numerical examples. Finally, it examines exactly what goes wrong when the coprimality hypothesis fails.

Key takeaways

An inverse of $a$ modulo $n$ is a residue $b$ with $ab \equiv 1 \pmod n$ ; when it exists it is unique modulo $n$ .
The inverse of $a$ mod $n$ exists if and only if $\gcd(a,n) = 1$ .
Existence is proved via Bezout's Identity: $\gcd(a,n)=1$ gives integers $x,y$ with $ax+ny=1$ , so $x$ is the inverse.
The Extended Euclidean Algorithm computes this $x$ efficiently, in $O(\log n)$ arithmetic steps.
The invertible residues mod $n$ form a group under multiplication, denoted $(\mathbb{Z}/n\mathbb{Z})^{\times}$ , of order $\varphi(n)$ .
Key idea: modular division by $a$ is well-defined precisely on the units of $\mathbb{Z}/n\mathbb{Z}$ , and Bezout's identity turns the abstract existence statement into an explicit, computable inverse.

Where this lives today

Modular inverses are the computational backbone of RSA and elliptic-curve cryptography: key generation and decryption both require computing an inverse modulo a large composite or prime, almost always via the extended Euclidean algorithm rather than brute force, because brute force is infeasible for numbers with hundreds of digits. In error-correcting codes and finite-field arithmetic (e.g. Reed–Solomon codes), inverses in $\mathbb{F}_p$ or $\mathbb{F}_{p^k}$ are needed at every decoding step. In computer algebra systems, solving linear congruences and systems of congruences via the Chinese Remainder Theorem reduces to computing inverses in each modulus. In hashing and pseudorandom number generation, invertibility modulo the table size or modulus ensures certain linear maps remain bijective, which is essential for full-period linear congruential generators. The same existence criterion also foreshadows The Order of an Element in $(\mathbb{Z}/n\mathbb{Z})^{\times}$ , Wilson's Theorem's use of inverse-pairing among residues modulo a prime, and general Linear Congruences theory, where solving $ax \equiv b \pmod n$ reduces immediately to multiplying both sides by $a^{-1}$ whenever it exists.

Ask the tutor: How does the extended Euclidean algorithm's back-substitution actually produce the coefficients $x, y$ in Bezout's identity, step by step, for a modulus of my choosing?

n

Intuition

Ordinary division by a nonzero integer $a$ is a global operation on $\mathbb{Q}$ : every nonzero rational number has a reciprocal. Modular arithmetic is different because $\mathbb{Z}/n\mathbb{Z}$ is a finite ring with zero divisors when $n$ is composite — for instance $2 \cdot 3 \equiv 0 \pmod 6$ , yet neither $2$ nor $3$ is $0$ . In such a ring, not every nonzero element can have a reciprocal, since if $a$ had an inverse $b$ and $ac \equiv 0$ with $c \not\equiv 0$ , multiplying by $b$ would force $c \equiv 0$ , a contradiction. So zero divisors are never invertible, and the question becomes: which residues escape being zero divisors entirely? The answer is visible already in the structure of the complete residue system $\{0, 1, \dots, n-1\}$ . Picture multiplication by $a$ as a function on this set. If $\gcd(a,n) = d > 1$ , then every multiple of $a$ modulo $n$ is automatically a multiple of $d$ (since $a$ is), so the map $x \mapsto ax \bmod n$ can never hit $1$ when $d \nmid 1$ . Coprimality removes this obstruction entirely, and Bezout's identity shows the obstruction is the only one: the linear combinations $ax + ny$ range exactly over the multiples of $\gcd(a,n)$ , so $1$ is achievable precisely when $\gcd(a,n)=1$ .

Figure

Multiplication-by-

a

as a permutation of residues, contrasted with a non-invertible case

Intuition (continued): the Euclidean algorithm as a search for the inverse

The extended Euclidean algorithm gives more than an abstract existence proof: it is an efficient constructive method. Running the Euclidean algorithm on $(a, n)$ backward through its sequence of remainders expresses $\gcd(a,n)$ as an integer combination $ax + ny$ , and reducing $x$ modulo $n$ produces the inverse directly — no search over $\{0, \dots, n-1\}$ required.

n

\Leftarrow

n

[a]

Worked examples

Example 1: Inverse of 17 modulo 43. First confirm $\gcd(17, 43) = 1$ . Since $43$ is prime and $17 \ne 43$ , this is immediate, but let us verify with the Euclidean algorithm, since we need its steps anyway:

43 = 2 \cdot 17 + 9

17 = 1 \cdot 9 + 8

9 = 1 \cdot 8 + 1

8 = 8 \cdot 1 + 0.

The last nonzero remainder is $1$ , confirming $\gcd(17,43) = 1$ , so an inverse exists. Now back-substitute to write $1$ as an integer combination of $17$ and $43$ :

1 = 9 - 1\cdot 8

= 9 - 1\cdot(17 - 1\cdot 9) = 2\cdot 9 - 1\cdot 17

= 2\cdot(43 - 2\cdot 17) - 1\cdot 17 = 2\cdot 43 - 5\cdot 17.

17\cdot(-5) + 43\cdot 2 = 1,

which reads $17 \cdot (-5) \equiv 1 \pmod{43}$ . Reducing $-5$ modulo $43$ gives $-5 + 43 = 38$ . So the inverse is

17^{-1} \equiv 38 \pmod{43}.

Check: $17 \times 38 = 646$ , and $646 = 15 \times 43 + 1$ since $15 \times 43 = 645$ . Indeed $646 - 645 = 1$ , confirming $17 \times 38 \equiv 1 \pmod{43}$ .

Example 2: Inverse of 24 modulo 91 — a case requiring the full algorithm on composite modulus. Here $91 = 7 \times 13$ . Check $\gcd(24, 91)$ via Euclid:

91 = 3 \cdot 24 + 19

24 = 1 \cdot 19 + 5

19 = 3 \cdot 5 + 4

5 = 1 \cdot 4 + 1

4 = 4 \cdot 1 + 0.

Last nonzero remainder is $1$ , so $\gcd(24, 91) = 1$ and the inverse exists (this also reconfirms independently that $24$ shares no factor with either $7$ or $13$ ). Back-substitute:

1 = 5 - 1\cdot 4

= 5 - 1\cdot(19 - 3\cdot 5) = 4\cdot 5 - 1\cdot 19

= 4\cdot(24 - 1\cdot 19) - 1\cdot 19 = 4\cdot 24 - 5\cdot 19

= 4\cdot 24 - 5\cdot(91 - 3\cdot 24) = 19\cdot 24 - 5\cdot 91.

So $24 \cdot 19 - 91\cdot 5 = 1$ , giving

24^{-1} \equiv 19 \pmod{91}.

Check: $24 \times 19 = 456$ . Divide: $456 = 5\times 91 + 1$ , since $5 \times 91 = 455$ . So $456 - 455 = 1$ , confirming $24 \times 19 \equiv 1 \pmod{91}$ .

Figure

Back-substitution unwinding the Euclidean algorithm for 24 and 91

a = 6

Scope, edge cases & common traps

Situation	What happens	Why
$\gcd(a,n) = 1$	Unique inverse mod $n$ exists	Bezout's identity, theorem above
$\gcd(a,n) = d > 1$	No inverse exists	$d \mid (ab-1)$ forces $d=1$ , contradiction
$n$ prime, $a \not\equiv 0$	Inverse always exists	$\gcd(a,n)=1$ automatic since $n$ prime
$a \equiv 0 \pmod n$ , $n>1$	No inverse (special case of $d=n>1$ )	$0 \cdot b \equiv 0 \not\equiv 1$
Working with negative $a$	Reduce $a \bmod n$ first; theorem is stated for the residue class	Congruence only depends on residue class
$n = 1$	Every integer is "invertible" trivially, since all integers are $\equiv 0 \equiv 1 \pmod 1$	Degenerate ring with one element

The mathematician behind it

Origins · 1 minÉtienne Bézout and how this was discovered

ÉB

Étienne Bézout

1730–1783 · French mathematician, Académie des Sciences

Bézout is best remembered for Bézout's identity and Bézout's theorem in algebraic geometry, both expressing the same intuition: that the "size" of an intersection or combination is governed by a greatest common divisor or a product of degrees. His systematic study, in the 1770s, of the integer solvability of $ax+by=c$ gave the theoretical machinery — later streamlined via the Euclidean algorithm — that makes the existence of modular inverses a one-line consequence rather than a case-by-case verification.

History

- c. 300 BCE — Euclid's Elements Book VII describes the algorithm for the greatest common divisor that underlies all later computation of modular inverses.

- 1621 — Bachet de Méziriac publishes a coefficient-finding procedure equivalent to solving

ax+by=\gcd(a,b)

, anticipating Bezout's identity.

- 1770s — Étienne Bézout formalizes and generalizes the identity bearing his name for integer (and polynomial) linear combinations.

- 1801 — Gauss's Disquisitiones Arithmeticae systematizes congruence notation and treats invertible residues as the foundation of modular arithmetic.

- 20th century — the extended Euclidean algorithm becomes a core primitive in computational number theory and cryptography, used explicitly to compute modular inverses at scale.

Does every nonzero residue modulo

n

have an inverse?

Only when $n$ is prime. If $n$ is prime, every $a$ with $1 \le a \le n-1$ automatically satisfies $\gcd(a,n)=1$ , since $n$ 's only divisors are $1$ and $n$ itself, and $a<n$ rules out $n$ . So modulo a prime, every nonzero residue is invertible, and $(\mathbb{Z}/p\mathbb{Z})^{\times}$ has all $p-1$ nonzero classes as units. For composite $n$ , this fails: any $a$ sharing a common prime factor with $n$ is a zero divisor and has no inverse, as shown in the counterexample with $6$ modulo $15$ .

How do I actually compute a modular inverse by hand efficiently?

Run the Euclidean algorithm on $(a,n)$ to obtain a sequence of quotients and remainders down to $\gcd(a,n)=1$ , then back-substitute from the last nontrivial step upward to express $1 = ax + ny$ for some integers $x,y$ . The residue of $x$ modulo $n$ is the inverse. This is the extended Euclidean algorithm, and it runs in time proportional to the number of steps in the ordinary Euclidean algorithm, which is $O(\log \min(a,n))$ divisions — dramatically faster than testing every residue.

Is the modular inverse the same as

1/a

as a real number reduced mod

n

No — there is no meaningful reduction of the real number $1/a$ modulo $n$ since $1/a$ typically is not an integer. The modular inverse is a genuinely different integer $b$ , found by solving $ab \equiv 1 \pmod n$ , and it has nothing to do with rounding or truncating the real reciprocal. For instance $7^{-1} \equiv 15 \pmod{26}$ , which bears no numerical resemblance to $1/7 \approx 0.142857$ .

What happens if I try to invert 0 modulo n, for n > 1?

It never has an inverse. Since $0 \cdot b \equiv 0 \pmod n$ for every $b$ , and $0 \not\equiv 1 \pmod n$ whenever $n > 1$ , no $b$ can satisfy $0\cdot b\equiv 1$ . This matches the theorem: $\gcd(0,n) = n$ , which equals $1$ only when $n=1$ , a degenerate modulus where every congruence is trivially true.

Can an element have more than one inverse modulo n?

No, and this is the content of the uniqueness half of the theorem. If $b_1$ and $b_2$ both invert $a$ modulo $n$ , then $a(b_1-b_2) \equiv 0 \pmod n$ , and because $\gcd(a,n)=1$ this forces $n \mid (b_1-b_2)$ , i.e. $b_1\equiv b_2 \pmod n$ . So while there are infinitely many integers representing the inverse (e.g. $\dots, -8, 38, 81,\dots$ all represent the same class modulo $43$ in Example 1), there is exactly one residue class.

How does this relate to solving general linear congruences

ax \equiv b \pmod n

Once you know $a^{-1}$ exists (i.e., $\gcd(a,n)=1$ ), you solve $ax\equiv b\pmod n$ by multiplying both sides by $a^{-1}$ , giving the unique solution $x \equiv a^{-1}b \pmod n$ . When $\gcd(a,n) = d > 1$ , the congruence needs a separate, more general treatment: it has solutions only if $d \mid b$ , and then there are exactly $d$ solutions modulo $n$ . That fuller theory is the subject of Linear Congruences, and it builds directly on the existence criterion proved here.

Why is coprimality with n, rather than with any particular prime factor, the right condition?

Because $\gcd(a,n)=1$ is exactly equivalent to $a$ sharing no prime factor with $n$ at all — if $a$ shared even one prime factor $p$ of $n$ , that $p$ would divide $\gcd(a,n)$ , blocking invertibility, as the necessity proof shows via divisibility of $ab-1$ . Conversely, having no shared prime factor is precisely what Bezout's identity requires and delivers: $\gcd(a,n)=1$ is the necessary and sufficient condition, not merely coprimality with some factor or most factors.