Bézout's identity: Visual walkthrough — Maths deep dive

This is the picture-companion to the parent note. If a word here feels new, we define it the moment it appears.

Step 0 — The one idea in a sentence

Let me make "adding copies" concrete before any algebra.

Step 1 — What "a linear combination" looks like

WHAT. Fix $a = 12$ and $b = 8$ . Line up jumps of size $12$ (rightward) and size $8$ (rightward). By combining them — some forward, some backward — we land on various points on the number line.

WHY. Every value $12 x + 8 y$ is just "walk $x$ jumps of 12 and $y$ jumps of 8". Understanding which landing points are reachable is the whole game. A linear combination of $a$ and $b$ is any number of the form $a x + b y$ with $x, y$ whole numbers.

PICTURE. Watch where the jumps land.

$12 x + 8 y : x = 1, y = - 1 \Rightarrow = 4 12 - 8, x = - 1, y = 2 \Rightarrow = 4 - 12 + 16$

Notice every landing point is a multiple of $4$ — never $3$ , never $5$ . That " $4$ " is exactly $g cd (12, 8)$ , and it is the smallest positive place we can land. Hold that observation; the whole proof explains it.

Step 2 — Collect all the positive landing points into a bag

WHAT. Define the set $S = {a landing point a x + b y : x, y \in Z, keep only the positive ones a x + b y > 0}$ Here $Z$ just means "all whole numbers …, $- 2, - 1, 0, 1, 2, \dots$ ".

WHY. We want the smallest positive thing we can build. So gather every positive buildable number into one bag $S$ and later reach in for the smallest.

PICTURE. $S$ is the set of red dots to the right of zero.

We must check the bag isn't empty — you can't pick the smallest thing from nothing.

Step 3 — Grab the smallest coin in the bag, call it $d$

WHAT. Let $d$ be the smallest number in $S$ . Write down the counters that produce it: $d = a fixed counter x_{0} + b fixed counter y_{0}$

WHY. A bag of positive whole numbers always has a smallest one — this is the Well-Ordering Principle ("every non-empty set of positive integers has a least element"). It's the tool that lets us say "the smallest" and know it exists.

PICTURE. $d$ is the leftmost red dot to the right of zero.

We now have a candidate. We will prove two things: (A) $d$ divides both $a$ and $b$ , and (B) $d$ is the greatest such divisor. Together: $d = g cd (a, b)$ .

Step 4 — Show $d$ divides $a$ (the heart of the proof)

WHAT. Split $a$ into as many whole $d$ -steps as fit, plus a leftover $r$ . This is the Division Algorithm: for any $a$ and positive $d$ , $a = how many d -steps q \cdot d + leftover r, leftover is smaller than d 0 \leq r < d$

WHY. If the leftover $r$ turned out to be a positive buildable number, it would be smaller than $d$ yet inside $S$ — impossible, since $d$ was the smallest. So $r$ must be $0$ , which means $d$ divides $a$ perfectly.

PICTURE. The leftover $r$ is the short red gap that refuses to fit.

Now the key trick — rewrite the leftover as a landing point. Substitute $d = a x_{0} + b y_{0}$ : $r = a - q d = a - q (a x_{0} + b y_{0}) = copies of a a (1 - q x_{0}) + copies of b b (- q y_{0})$

So $r$ is of the form $a x + b y$ — it's buildable! Two cases:

If $r > 0$ : then $r \in S$ and $r < d$ , contradicting " $d$ is smallest." Forbidden.
Therefore $r = 0$ , i.e. $a = q d$ , i.e. $d ∣ a$ . ✓

By the identical argument with $b$ in place of $a$ , we also get $d ∣ b$ . So $d$ is a common divisor.

Step 5 — Show $d$ is the greatest common divisor

WHAT. Let $c$ be any common divisor of $a$ and $b$ . We show $c ∣ d$ , so no common divisor can exceed $d$ .

WHY. "Greatest common divisor" means every other common divisor fits inside it. If every $c$ divides $d$ , then $d$ is at least as big as any $c$ — it's the greatest.

PICTURE. Any $c$ -ruler that measures both $a$ and $b$ also measures their combination $d$ .

Since $c ∣ a$ and $c ∣ b$ , write $a = c m$ and $b = c n$ . Then $d = a x_{0} + b y_{0} = a c m x_{0} + b c n y_{0} = c (a whole number m x_{0} + n y_{0}) .$ The right side is $c$ times a whole number, so $c ∣ d$ . Any common divisor divides $d$ ⟹ $d$ is the greatest.

Conclusion. $d$ is a common divisor (Step 4) and the greatest one (Step 5), so $g cd (a, b) = d = a x_{0} + b y_{0}$ which is Bézout's Identity. □

Step 6 — The degenerate cases (never leave a gap)

WHAT & WHY. The proof assumed "not both zero" and used a positive smallest element. Let's walk the corner cases so no reader hits an unshown scenario.

Step 7 — Reading a worked example through the proof's eyes

The Extended Euclidean Algorithm is just Step 4's division-with-remainder run repeatedly, then read backwards. Take $a = 240, b = 46$ :

240 &= 46\cdot 5 + 10\\ 46 &= 10\cdot 4 + 6\\ 10 &= 6\cdot 1 + 4\\ 6 &= 4\cdot 1 + 2\\ 4 &= 2\cdot 2 + 0 \end{aligned}$$ The last non-zero remainder is $2=\gcd(240,46)$ — that's the smallest positive landing point $d$. Back-substituting rebuilds it as a combination: $$2 \;=\; 240\cdot(\underbrace{-9}_{x}) + 46\cdot(\underbrace{47}_{y}).$$ > [!recall]- Check the arithmetic yourself > $240(-9)+46(47) ::: -2160+2162 = 2$ ✓ — matches $\gcd(240,46)=2$. And solutions aren't unique — shift by $b/d=23$ and $a/d=120$ (see [[Linear Diophantine Equations]]): $$x=-9+23k,\qquad y=47-120k.$$ For $k=1$: $x=14,\ y=-73$, and $240(14)+46(-73)=3360-3358=2$. ✓ > [!recall]- Why the two counters $x,y$ aren't unique > Which counter shift leaves $ax+by$ unchanged? ::: $x\to x+\tfrac{b}{d}k,\ y\to y-\tfrac{a}{d}k$; the extra terms are $+\tfrac{ab}{d}k-\tfrac{ab}{d}k=0$. --- ## The one-picture summary The whole derivation in one glance: build the bag $S$ of positive combinations → its smallest member $d$ divides both $a$ and $b$ (leftover-would-be-smaller trick) → any common divisor divides $d$ → therefore $d=\gcd(a,b)=ax_0+by_0$. ```mermaid flowchart TD A["Bag S of positive ax plus by"] --> B["Smallest element d exists"] B --> C["Divide a by d leftover r"] C --> D["r is also a combination"] D --> E["r must be 0 so d divides a and b"] E --> F["Any common divisor c divides d"] F --> G["d equals gcd equals a x0 plus b y0"] ``` > [!recall]- Feynman retelling — say it plain > I've got two step-sizes, $a$ and $b$. By stepping forward and back I can land on lots of numbers. I toss all the *positive* landing spots into a bag. That bag has a smallest number — call it $d$. Now here's the punchline: if I try to measure $a$ using rulers of length $d$, any leftover bit would *also* be a landing spot, but smaller than $d$ — and $d$ was the smallest, so there can be *no* leftover. That means $d$ divides $a$ cleanly, and the same for $b$. Finally, anything that divides both $a$ and $b$ automatically divides my combination $d$, so nothing bigger than $d$ can be a common divisor. Smallest-positive-landing-spot = greatest-common-divisor. That's Bézout. > [!mnemonic] Remember the whole thing > **"Smallest built = greatest that divides."** The tiniest positive number you can *make* from $a$ and $b$ is the biggest number that *fits into* both. --- **Prerequisites revisited:** [[Euclidean Algorithm]] · [[Greatest Common Divisor]] · [[Modular Arithmetic]] · back to [[Bézout's identity]].