Bezout's Identity

The Euclidean Algorithm computes $\gcd(a, b)$. But what is $\gcd(a, b)$?

"The largest number dividing both" is a correct definition. It's not an illuminating one. Here is the illuminating one:

$\gcd(a, b)$ is the smallest positive integer of the form $ax + by$, where $x$ and $y$ are integers.

This is Bezout's Identity. It reframes the GCD from a property of division into a property of reachability — which integers can you construct from $a$ and $b$ using addition and subtraction?

---

The theorem

Bezout's Identity. For any integers $a, b$ not both zero, there exist integers $x, y$ such that:

$ax + by = \gcd(a, b)$

And the set $\{ax + by : x, y \in \mathbb{Z}\}$ is exactly the set of all multiples of $\gcd(a, b)$.

---

Finding the coefficients — back-substitution

Run the Euclidean Algorithm. Then read the steps backwards.

Example. Find integers $x, y$ such that $1071x + 462y = 21$.

First, run the Euclidean Algorithm:

1071 = 2 \times 462 + 147 \tag{1} 462 = 3 \times 147 + 21 \tag{2} 147 = 7 \times 21 + 0 \tag{3}

So $\gcd(1071, 462) = 21$.

Now back-substitute. From (2): $21 = 462 - 3 \times 147$.

From (1): $147 = 1071 - 2 \times 462$.

Substitute:

$21 = 462 - 3(1071 - 2 \times 462) = 7 \times 462 - 3 \times 1071$

So $x = -3$, $y = 7$. Check: $1071(-3) + 462(7) = -3213 + 3234 = 21$. ✓

---

The key consequence

Corollary. If $d \mid a$ and $d \mid b$, then $d \mid \gcd(a, b)$.

Proof. Since $\gcd(a,b) = ax + by$ for some integers $x, y$, and $d$ divides both $a$ and $b$, we get $d \mid ax + by = \gcd(a,b)$. $\blacksquare$

This is what earns the word greatest. Every common divisor of $a$ and $b$ divides $\gcd(a,b)$ — so $\gcd(a,b)$ is genuinely the largest.

Without Bezout, "greatest" is just a claim. With Bezout, it's a theorem.

---

What the set $\{ax + by\}$ looks like

Let $d = \gcd(a, b)$. The set of all integers expressible as $ax + by$ is:

$\{\ldots, -2d, -d, 0, d, 2d, 3d, \ldots\} = d\mathbb{Z}$

Exactly the multiples of $d$, nothing more, nothing less.

Why nothing less than $d$? Any $ax+by$ is divisible by $d$ (since $d \mid a$ and $d \mid b$), so no element of the set is smaller than $d$ in absolute value.

Why $d$ is reachable? Bezout says so directly.

Why all multiples of $d$ are reachable? If $ax_0 + by_0 = d$, then $a(nx_0) + b(ny_0) = nd$ for any integer $n$.

---

Euclid's Lemma — the payoff

This is the most important application of Bezout at JEE Advanced level.

Euclid's Lemma. If $\gcd(a, b) = 1$ and $a \mid bc$, then $a \mid c$.

Proof. From Bezout: $ax + by = 1$ for some integers $x, y$. Multiply both sides by $c$:

$acx + bcy = c$

$a \mid ac$ and $a \mid bc$ (given), so $a \mid acx + bcy = c$. $\blacksquare$

The prime case. If $p$ is prime and $p \mid ab$, then $p \mid a$ or $p \mid b$.

Proof. If $p \nmid a$, then $\gcd(p, a) = 1$ (since $p$ is prime, its only divisors are 1 and $p$). Euclid's lemma then forces $p \mid b$. $\blacksquare$

This is the fact that makes prime factorization unique. Uniqueness of the Fundamental Theorem of Arithmetic rests entirely on this lemma.

---

Worked problems

Problem 1. Prove: if $\gcd(a,b)=1$ and $a \mid n$ and $b \mid n$, then $ab \mid n$.

Write $n = ak$ for some integer $k$. Then $b \mid ak$ and $\gcd(a,b)=1$, so by Euclid's lemma, $b \mid k$. Write $k = bm$. Then $n = abm$, so $ab \mid n$. $\blacksquare$

Problem 2. Prove: $\gcd(a^2, b^2) = \gcd(a,b)^2$.

Let $d = \gcd(a,b)$, $a = dp$, $b = dq$, $\gcd(p,q) = 1$.

Then $a^2 = d^2 p^2$, $b^2 = d^2 q^2$. We need $\gcd(p^2, q^2) = 1$.

Suppose prime $r \mid p^2$. Then $r \mid p$. If also $r \mid q^2$, then $r \mid q$. But then $r \mid \gcd(p,q) = 1$, contradiction. So $\gcd(p^2, q^2) = 1$, giving $\gcd(a^2, b^2) = d^2$. $\blacksquare$

Problem 3. Find all integers $n$ such that $n+1 \mid n^2 + 1$.

Write $n^2 + 1 = (n+1)(n-1) + 2$. So if $n+1 \mid n^2+1$ then $n+1 \mid 2$.

Thus $n+1 \in \{-2, -1, 1, 2\}$, giving $n \in \{-3, -2, 0, 1\}$.

Problem 4. Prove that $\gcd(a,b) \cdot \gcd(a,c) \geq \gcd(a, bc)$ when $\gcd(b,c)=1$.

Actually the stronger result holds: $\gcd(a, bc) = \gcd(a,b) \cdot \gcd(a,c)$ when $\gcd(b,c)=1$.

Let $d_1 = \gcd(a,b)$, $d_2 = \gcd(a,c)$. Write $a = d_1 s = d_2 t$. Show $d_1 d_2 \mid a$ and $d_1 d_2 \mid bc$, and that $\gcd(a/d_1, c) = \gcd(s, c)$... the full proof uses Euclid's lemma iteratively.

---

Edge cases worth naming

• $\gcd(0, 0)$ is undefined (or sometimes set to 0 by convention). Bezout fails here.
• The Bezout coefficients $x, y$ are not unique. If $(x_0, y_0)$ works, so does $(x_0 + b/d, y_0 - a/d)$ for any integer multiple. The general solution is exactly the theory of Linear Diophantine Equations.
• Bezout gives existence of coefficients. Finding them requires the Extended Euclidean Algorithm (back-substitution above). Don't confuse the theorem with the algorithm.

---

The next natural question: since $ax + by$ spans all multiples of $\gcd(a,b)$, what happens when you fix the right-hand side and ask for all solutions? That's the complete theory of $ax + by = c$ — which lives in Linear Diophantine Equations.