In ordinary arithmetic, every non-zero number has a reciprocal. 7 has \tfrac{1}{7}. -3 has -\tfrac{1}{3}. You never have to stop and wonder whether the reciprocal exists — it just does, somewhere on the number line.

Modular arithmetic does not grant you that. In \mathbb{Z}/n\mathbb{Z} — the world of residues mod n — some non-zero elements have a multiplicative inverse and some do not. "Having an inverse" means having some residue x with a \cdot x \equiv 1 \pmod n, so that dividing by a is legal and a^{-1} is a real object you can name. The question "when does this inverse exist?" has a single, sharp answer:

a has a multiplicative inverse mod n if and only if \gcd(a, n) = 1.

That one line is the gate. Every downstream fact about invertibility, fields, linear congruences, and RSA passes through it.

Why coprimality is the exact condition

The argument rests on a classical identity from number theory: Bezout's identity. Given any two integers a and n, there exist integers x and y such that

a x + n y = \gcd(a, n).

The extended Euclidean algorithm actually constructs x and y — it is not an existence proof you have to take on faith.

Now suppose \gcd(a, n) = 1. Bezout gives a x + n y = 1 for some integers x, y. Reduce this mod n: the n y term disappears (it is a multiple of n, so it is \equiv 0 \pmod n), and you get

a x \equiv 1 \pmod n.

That x is exactly the multiplicative inverse of a mod n. It exists, and Bezout's identity hands it to you constructively.

Conversely, suppose \gcd(a, n) = g > 1. Could a still have an inverse? If a x \equiv 1 \pmod n, then n \mid (a x - 1), so there is some integer k with a x - 1 = n k, i.e. a x - n k = 1. But g divides the left side — g \mid a and g \mid n, so g divides any integer linear combination a x - n k. That forces g \mid 1, which is impossible for g > 1. So no inverse exists.

Why the two halves line up: Bezout says \gcd(a, n) is the smallest positive integer you can write as a x + n y. Being able to write 1 that way is equivalent to \gcd(a, n) = 1 — which in turn is equivalent to having an inverse. The three statements "coprime," "writable as a x + n y = 1," and "has an inverse mod n" are mutually equivalent.

The mod-10 inverse table

Mod 10 is the cleanest place to see both invertible and non-invertible residues side by side. The residues are \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}, and the invertible ones are exactly those coprime to 10.

Factoring 10 = 2 \times 5: a residue is coprime to 10 exactly when it is neither even nor a multiple of 5. Four residues survive: \{1, 3, 7, 9\}. Six residues (0, 2, 4, 5, 6, 8) fail the gcd test and have no inverse.

Invertible and non-invertible residues mod 10A row of ten boxes labelled 0 through 9. The boxes for 1, 3, 7, and 9 are highlighted as invertible with their inverses noted: 1 inverse 1, 3 inverse 7, 7 inverse 3, 9 inverse 9. The boxes for 0, 2, 4, 5, 6, 8 are shaded as not invertible with a note that each shares a factor with 10. ℤ/10ℤ — which residues have a multiplicative inverse? 0 1 2 3 4 5 6 7 8 9 gcd 10 gcd 1 gcd 2 gcd 1 gcd 2 gcd 5 gcd 2 gcd 1 gcd 2 gcd 1 1⁻¹ = 1 3⁻¹ = 7 7⁻¹ = 3 9⁻¹ = 9 Only the 4 residues coprime to 10 are invertible. The count φ(10) = 4 is exactly Euler's totient.
The ten residues mod $10$, split into invertible (highlighted) and non-invertible. The four invertible ones are exactly those coprime to $10$; their inverses pair up as $1 \leftrightarrow 1$, $3 \leftrightarrow 7$, $9 \leftrightarrow 9$. The six non-invertible residues each share a factor (either $2$ or $5$) with $10$.

Computing 3^{-1} mod 10 with the extended Euclidean algorithm

Let us actually find the inverse of 3 mod 10, not just claim it exists. The extended Euclidean algorithm runs the normal Euclidean gcd algorithm forward, then back-substitutes to produce Bezout coefficients.

Forward pass (Euclidean algorithm on 10, 3):

The gcd is 1 (the last non-zero remainder). Because \gcd(3, 10) = 1, we already know an inverse exists.

Back-substitution for Bezout coefficients:

From the first line: 1 = 10 - 3 \cdot 3. That is already the Bezout identity:

1 = 10 \cdot 1 + 3 \cdot (-3).

So x = -3 and y = 1. Reduce x mod 10: -3 \equiv 7 \pmod{10}. Check: 3 \cdot 7 = 21 = 2 \cdot 10 + 1 \equiv 1 \pmod{10}. ✓

Therefore 3^{-1} \equiv 7 \pmod{10}. The extended Euclidean algorithm did not just tell you an inverse exists; it produced the inverse explicitly in two lines.

Why 2^{-1} mod 10 does not exist

Now consider the residue 2. \gcd(2, 10) = 2 > 1, so the rule predicts no inverse. But let us see the failure directly.

Look at the multiplication row for 2 mod 10:

2 \cdot 0 = 0,\ 2 \cdot 1 = 2,\ 2 \cdot 2 = 4,\ 2 \cdot 3 = 6,\ 2 \cdot 4 = 8,\ 2 \cdot 5 = 10 \equiv 0, \ldots

The full row reads 0, 2, 4, 6, 8, 0, 2, 4, 6, 8. It hits only even residues — never 1, 3, 5, 7, 9. No matter what x you pick, 2 x \pmod{10} is even, and 1 is odd. So 2 x \equiv 1 \pmod{10} has no solution.

Why this is structural, not accidental: if \gcd(a, n) = g, then the set \{a \cdot x \bmod n : x = 0, 1, \ldots, n - 1\} consists only of multiples of g, and there are exactly n / g of them. Only g = 1 lets that set cover everything up to n - 1 and hit 1.

The prime modulus payoff: every non-zero residue is invertible

The rule "invertible iff coprime to n" has a spectacular consequence when n is prime. If p is prime, then every integer from 1 to p - 1 is coprime to p (primes have no proper divisors to share with). So every non-zero residue mod p has a multiplicative inverse.

That is not a small thing. It is exactly the property that makes \mathbb{Z}/p\mathbb{Z} a field — a number system where you can divide by anything non-zero, just like \mathbb{Q} or \mathbb{R}. You can solve linear equations, do Gaussian elimination, define vector spaces, and build polynomial quotient rings — all the machinery of linear algebra and Galois theory transfers over.

For composite n, the structure \mathbb{Z}/n\mathbb{Z} is still a ring, but not a field. Only the subset of coprime residues forms a group under multiplication. That subset is called (\mathbb{Z}/n\mathbb{Z})^\times, and its size is Euler's totient \varphi(n) — the number of integers from 1 to n that are coprime to n. For n = 10, \varphi(10) = 4, matching the four invertible residues you saw above.

The connection to RSA

RSA public-key cryptography rests entirely on this gate. The set-up picks two large primes p, q and sets n = p q. The encryption exponent e is chosen coprime to \varphi(n) = (p - 1)(q - 1), precisely so that e has an inverse d modulo \varphi(n) — that is, e d \equiv 1 \pmod{\varphi(n)}.

Why does that inverse d matter? Because encryption is c = m^e \bmod n, and decryption is m = c^d \bmod n. By Euler's theorem, m^{e d} \equiv m \pmod n when e d \equiv 1 \pmod{\varphi(n)} — so d "undoes" e. The whole scheme works if and only if d exists, and d exists if and only if \gcd(e, \varphi(n)) = 1.

If RSA picked e with \gcd(e, \varphi(n)) > 1, there would be no decryption key, and the cipher would be unusable. This is why RSA implementations run the extended Euclidean algorithm on (e, \varphi(n)) during key generation — not only to verify coprimality, but to produce d explicitly.

The gate "inverse exists iff coprime" is so central to modern cryptography that the Diffie-Hellman protocol, ElGamal encryption, elliptic-curve cryptography, and digital signatures all rely on it in some form. The humble gcd condition you learned in grade-school number theory holds up the infrastructure of internet banking.

The one-line summary

a^{-1} exists in \mathbb{Z}/n\mathbb{Z} if and only if \gcd(a, n) = 1, and when it exists the extended Euclidean algorithm computes it. For prime n, every non-zero residue qualifies, making \mathbb{Z}/p\mathbb{Z} a field. For composite n, only the \varphi(n) residues coprime to n are invertible — and RSA's security depends on picking its exponent from exactly that subset.

Related: Modular Arithmetic · To Divide a Congruence, the Divisor Must Be Coprime to the Modulus · Modular Inverse Finder · Mod 7 Multiplication Table — Why ℤ/7ℤ Is a Field · Number Theory Basics