gcd(a, b) = 1 Is a Signal — Bézout and Modular Inverses Are Now Free Tools

In number theory, a single condition can unlock two theorems at once, and if you are fluent, you reach for those theorems on reflex. The condition is \gcd(a, b) = 1 — the two integers are coprime — and the tools it hands you are:

Bézout's identity. There exist integers x, y such that ax + by = 1.
Modular inverses. There exists an integer a^{-1} with a \cdot a^{-1} \equiv 1 \pmod b, and similarly b^{-1} mod a.

The second is really a repackaging of the first — reduce Bézout's equation mod b and you get ax \equiv 1 \pmod b, so x is the inverse of a. But the recognition move matters: whenever you see "coprime" in a problem statement, your hand should already be writing ax + by = 1 or a \cdot a^{-1} \equiv 1 \pmod b. This reflex solves an enormous class of problems almost mechanically.

Why "coprime" is such a loud signal

Coprimality is a surprisingly strong condition. It says that a and b share no prime factor. In the exponent-vector picture where each integer is indexed by its prime factorisation, coprime means the two vectors have disjoint support — they live in completely different prime coordinates.

That disjointness has concrete consequences:

a cannot be "cancelled" from b in any factorisation.
The map x \mapsto ax \pmod b is a bijection on \{0, 1, 2, \ldots, b-1\} (equivalently, on \mathbb{Z}/b\mathbb{Z}).
Congruence equations ax \equiv c \pmod b have a unique solution mod b for every c.
If ab \mid N, then a \mid (N/b) without any loss.

Every one of these facts fails the moment \gcd(a, b) > 1. So the presence of coprimality is structural information, not an afterthought.

The first tool: Bézout's identity

Bézout's identity. If \gcd(a, b) = d, there exist integers x, y such that ax + by = d. In particular, if \gcd(a, b) = 1, there exist x, y with ax + by = 1.

Why: the Euclidean algorithm, run backwards, produces x and y explicitly. It is a constructive theorem, not an existence-only claim.

This equation is a sledgehammer. Whenever you can rewrite a problem as "find integer combinations of a and b," the equation ax + by = 1 tells you that every integer whatsoever can be written as a(xc) + b(yc) = c. In effect, coprime a and b generate the entire integer lattice under addition and subtraction.

A classic consequence: if a \mid bc and \gcd(a, b) = 1, then a \mid c. Proof: multiply Bézout by c to get acx + bcy = c. Both terms on the left are divisible by a (a \mid acx trivially, a \mid bcy because a \mid bc by hypothesis). So a \mid c. Done in two lines — impossible without the coprimality.

The second tool: modular inverses

The modular inverse is what you reach for when a problem lives in \mathbb{Z}/n\mathbb{Z} — modular arithmetic.

Modular inverse. If \gcd(a, n) = 1, there exists an integer a^{-1} (unique mod n) such that a \cdot a^{-1} \equiv 1 \pmod n.

The proof is two lines once Bézout is in hand: find x, y with ax + ny = 1. Reduce mod n: ax \equiv 1 \pmod n. So x \equiv a^{-1} \pmod n.

Why does this matter? Because division in modular arithmetic is normally forbidden, but with an inverse you can safely "divide" by multiplying by the inverse. Equations like 3x \equiv 7 \pmod{10} are instantly solvable: \gcd(3, 10) = 1, so 3^{-1} exists mod 10. You can find by inspection that 3 \cdot 7 = 21 \equiv 1 \pmod{10}, so 3^{-1} \equiv 7. Multiply both sides of 3x \equiv 7 by 7: x \equiv 49 \equiv 9 \pmod{10}.

No inverse, no division. The condition \gcd(3, 10) = 1 is what makes the trick work.

Interactive demo: coprime unlocks both tools

a: b:

Drag the $a$ and $b$ sliders. Extended Euclidean is run live: if $\gcd(a,b)=1$ you get Bézout coefficients $x, y$ with $ax + by = 1$ and $a^{-1} \equiv x \pmod b$. If $\gcd > 1$, both tools break — there is no $a^{-1}$ mod $b$. The grid highlights the multiples $a \cdot k \bmod b$; they hit $1$ exactly when coprime.

The reflex: three question types that light up on "coprime"

Here are problem signatures where you should feel the Bézout / inverse reflex kick in automatically.

1. Linear Diophantine equations

"Find all integer solutions to 7x + 11y = 3."

Read the coefficients: \gcd(7, 11) = 1. Solutions exist for any right-hand side. Use the Euclidean algorithm backwards to find one particular (x_0, y_0), then write the full family as (x_0 + 11t, y_0 - 7t) for t \in \mathbb{Z}. The coprimality is what guarantees solutions exist at all.

If instead the problem had 6x + 9y = 3, the gcd is 3, which divides 3 — solutions still exist, but now solutions exist only if the RHS is a multiple of 3. The coprime case is the "everything works" case.

2. Congruence equations

"Solve 11x \equiv 4 \pmod{15}."

Read: \gcd(11, 15) = 1. Inverse exists. Find it (11 \cdot 11 = 121 \equiv 1 \pmod{15}, so 11^{-1} \equiv 11). Multiply: x \equiv 4 \cdot 11 = 44 \equiv 14 \pmod{15}. Single-line solution.

Without the coprimality, the equation could have zero solutions (if \gcd \nmid 4) or multiple solutions (if \gcd \mid 4 but \gcd > 1). The coprime case is the one-solution, direct case.

3. The Chinese Remainder Theorem

"Find n with n \equiv 2 \pmod 7 and n \equiv 3 \pmod{11}."

Read the moduli: \gcd(7, 11) = 1. CRT applies. A unique solution mod 77 exists. The coprimality of the moduli is the hypothesis of the theorem — without it, CRT doesn't fire, and you would need a compatibility check on the residues.

A worked recognition example

Problem. Suppose a \mid bc and \gcd(a, b) = 1. Prove a \mid c. (This is Euclid's lemma, the key step in proving unique factorisation.)

Recognition. The hypothesis \gcd(a, b) = 1 is a flare. Reflex: write Bézout's identity for a and b: there exist integers x, y with

ax + by = 1.

Multiply both sides by c:

acx + bcy = c.

Now ask: does a divide the left side? Yes — a \mid acx trivially, and a \mid bcy because a \mid bc (given) and so a \mid (bc)y. Therefore a divides the sum, which is c. QED.

The whole proof is three lines once the Bézout reflex fires. Without the reflex, students often flounder for half a page.

When the reflex fails

Two subtleties to flag:

"Coprime" can hide. Sometimes a problem says "a and b have no common factor other than 1" or "a is not divisible by any prime factor of b." Same condition, different words. Train yourself to translate these into \gcd = 1 and deploy the tools.
Non-coprime versions still exist. If \gcd(a, b) = d > 1, Bézout still holds as ax + by = d, and you can solve congruences ax \equiv c \pmod b when d \mid c. These are "degraded" tools — usable but with the extra divisibility condition. Keep them in mind for gcd > 1 problems.

One-line takeaway

When a problem states \gcd(a, b) = 1, write ax + by = 1 on your scratch paper immediately. That single equation — Bézout's identity — unlocks modular inverses, linear Diophantine equations, the Chinese Remainder Theorem, and Euclid's lemma. "Coprime" is not decoration; it is an invitation to use the strongest tools in elementary number theory.