Extended Euclidean algorithm: Visual walkthrough

Before any symbol appears: here is the whole idea in one sentence. We chop a big number down using a small number over and over; and at every chop we quietly write down "how much of the big number and how much of the small number are hiding inside this leftover piece."

Throughout, $a$ and $b$ are non-negative integers (zero or positive whole numbers — no negatives), and for the very first division we need $b > 0$ so we actually have something to divide by. The single truly undefined corner, $g cd (0, 0)$ , is dealt with head-on in Step 7.

Step 1 — What "divide with remainder" really means

WHAT. With $a = 56$ , $b = 15$ : fit as many 15s into 56 as possible. Three of them: $3 \times 15 = 45$ . Left over: $56 - 45 = 11$ . So $q = 3$ , $r = 11$ .

WHY this operation and not, say, subtracting once? Because dividing does all the repeated subtractions in a single stroke. Subtracting 15 from 56 three times is the same as $56 - 3 \cdot 15$ ; the quotient $q = 3$ just counts how many times.

PICTURE. The bar of length 56 is covered by three teal blocks of 15, and one leftover orange stub of length 11 pokes out.

Step 2 — The chain of remainders (this is the Euclidean Algorithm)

WHAT. For $56$ and $15$ :

56151143 = 3 \cdot 15 + 11 = 1 \cdot 11 + 4 = 2 \cdot 4 + 3 = 1 \cdot 3 + 1 = 3 \cdot 1 + 0

The last non-zero remainder is $1$ , so $g cd (56, 15) = 1$ .

WHY it must terminate. Each remainder is strictly smaller than the one before ( $0 \leq r < b$ from Step 1). A strictly decreasing sequence of non-negative whole numbers can't go forever — it is forced to hit $0$ .

WHY the last non-zero remainder is the gcd. Let us give a name to the star of the argument: write $r_{last}$ for the last non-zero remainder — the final $r$ produced before the algorithm first hits $0$ (here $r_{last} = 1$ ). Now the "see why" argument as a picture-friendly chain. Suppose a number $d$ divides both $a$ and $b$ . Look at the first line $a = q b + r$ , rewritten as $r = a - q b$ . Since $d$ divides $a$ and $d$ divides $b$ , it divides $a - q b$ too — so $d$ divides $r$ . Now $d$ divides $b$ and $r$ , so by the same argument it divides the next remainder, and so on down every line. The implication marches all the way to the bottom:

$d ∣ a, d ∣ b \Rightarrow d ∣ r_{1} \Rightarrow d ∣ r_{2} \Rightarrow \dots \Rightarrow d ∣ r_{last} (r_{last} = last non-zero remainder) .$

Reading the chain upward does the reverse: the last non-zero remainder $r_{last}$ divides the one above it (the line where its multiple gives remainder $0$ ), which divides the next, all the way back up to $a$ and $b$ . So $r_{last}$ both divides $a, b$ and is divisible by every common divisor — that is exactly what "greatest common divisor" means.

PICTURE. A descending staircase of shrinking bars: $56 \to 15 \to 11 \to 4 \to 3 \to 1 \to 0$ . Each step's leftover becomes the next step's divisor (arrow pointing down-left).

Recall The divisibility chain in one line

Why does a common divisor $d$ of $a, b$ survive to the last non-zero remainder $r_{last}$ ? ::: Because $r = a - q b$ : if $d$ splits $a$ and $b$ cleanly it also splits their combination $r$ , and this repeats on every line, so $d$ divides every remainder down to the last non-zero one — which is the gcd.

Step 3 — The key idea: every leftover is a recipe in $a$ and $b$

WHAT. Look at the very first leftover: $11 = 56 - 3 \cdot 15$ . Rewrite it as $11 = x 1 \cdot 56 + y (- 3) \cdot 15.$ So the recipe for $11$ is $(x, y) = (1, - 3)$ : one copy of $56$ , minus three copies of $15$ .

WHY track this? Our goal is to write $g cd$ itself as $x \cdot a + y \cdot b$ . If every leftover carries such a recipe, then the last non-zero leftover — the gcd — arrives with its recipe already built. No backtracking needed.

PICTURE. The orange stub of length 11 is shown as "one full 56-bar, with three 15-blocks scrubbed away (hatched out)." Its recipe label reads $(1, - 3)$ .

Step 4 — The two seed recipes (the base cases)

WHAT. $a = 56$ gets the tag $(1, 0)$ ; $b = 15$ gets the tag $(0, 1)$ .

WHY these exactly? $56$ is trivially "one copy of $56$ and zero copies of $15$ ." These are the identity recipes — nothing has been mixed yet. If you skip them and start tagging only from the first division, the recurrence has nothing to feed on and collapses.

PICTURE. Two starting cards. Card $a$ : a full $56$ -bar labelled $(1, 0)$ . Card $b$ : a full $15$ -bar labelled $(0, 1)$ . These are the coordinate axes of everything that follows.

Step 5 — The recurrence: how a new recipe is born

WHAT. The identical arithmetic that made the new remainder ( $r_{i - 2} - q_{i} r_{i - 1}$ ) also makes the new recipe — you just run it separately on the $x$ -column and the $y$ -column.

WHY it works. A recipe is linear: if $A$ has recipe $(x_{A}, y_{A})$ and $B$ has $(x_{B}, y_{B})$ , then $A - q B$ has recipe $(x_{A} - q x_{B}, y_{A} - q y_{B})$ . Subtraction and scaling of $a, b$ -combinations stay $a, b$ -combinations. This is the whole engine.

PICTURE. Three columns — remainder, $x$ , $y$ — each computing "two positions back minus $q$ times one position back" with the same coloured arrows. The remainder column and the $x$ column and the $y$ column are visibly the same shape of arrow.

Step 6 — Run it: watch the recipes evolve to the gcd

WHAT. Start from the seeds $(1, 0)$ and $(0, 1)$ and apply Step 5 down every division line. The two seed rows ( $r_{0} = 56$ , $r_{1} = 15$ ) show "—" in the quotient column because no division has happened yet — they are the starting values, not results of a division, so there is no $q$ to record. The first real quotient, $q_{2} = 3$ , appears on the line that creates the first leftover $r_{2} = 11$ .

$i$	$r_{i}$	$q_{i}$	$x_{i}$	$y_{i}$	recipe check $56 x_{i} + 15 y_{i}$
$0$	$56$	— (seed, no division)	$1$	$0$	$56$
$1$	$15$	— (seed, no division)	$0$	$1$	$15$
$2$	$11$	$3$	$1 - 3 \cdot 0 = 1$	$0 - 3 \cdot 1 = - 3$	$56 - 45 = 11$
$3$	$4$	$1$	$0 - 1 \cdot 1 = - 1$	$1 - 1 \cdot (- 3) = 4$	$- 56 + 60 = 4$
$4$	$3$	$2$	$1 - 2 \cdot (- 1) = 3$	$- 3 - 2 \cdot 4 = - 11$	$168 - 165 = 3$
$5$	$1$	$1$	$- 1 - 1 \cdot 3 = - 4$	$4 - 1 \cdot (- 11) = 15$	$- 224 + 225 = 1$
$6$	$0$	$3$	stop	stop	—

WHY stop at $r_{5} = 1$ , not $r_{6} = 0$ ? The gcd is the last non-zero remainder. The row $i = 6$ has remainder $0$ ; the answer lives one row up, at $i = 5$ : $(x, y) = (- 4, 15)$ .

WHY the parentheses on signs? At $r_{4} = 3$ we needed $- 3 - 2 \cdot (4)$ but earlier $1 - 2 \cdot (- 1)$ . Writing the one-position-back value inside brackets with its sign stops the classic sign flip.

Result. $56 \cdot (- 4) + 15 \cdot 15 = - 224 + 225 = 1 = g cd (56, 15) . ✓$

PICTURE. The staircase from Step 2 re-drawn, but each stair now carries its evolving $(x, y)$ card, and the rightmost check column shows $56 x + 15 y$ landing back on the remainder every time — proof the invariant never breaks.

Step 7 — Edge and degenerate cases (never get surprised)

Worked example Every corner the algorithm can hit

Case A — $b ∣ a$ (one number divides the other). $g cd (12, 4)$ : the first division gives $12 = 3 \cdot 4 + 0$ . The remainder is $0$ immediately, so the gcd is $b = 4$ , with recipe $(0, 1)$ : $12 \cdot 0 + 4 \cdot 1 = 4$ .

Case B — one input is $0$ . $g cd (a, 0) = a$ . Nothing to divide; the recipe is the seed $(1, 0)$ : $a \cdot 1 + 0 \cdot 0 = a$ .

Case C — coprime inputs ( $g cd = 1$ ). Exactly our $g cd (56, 15) = 1$ . Here $x = - 4$ is the modular inverse of $56$ modulo $15$ (because $56 x \equiv 1 (mod 15)$ ), and $y = 15$ is the modular inverse of $15$ modulo $56$ (because $15 y \equiv 1 (mod 56)$ ). So $x$ inverts the first number mod the second, and $y$ inverts the second number mod the first.

Case D — $a < b$ at the start. No problem: the first division $a = 0 \cdot b + a$ has quotient $0$ , which simply swaps them. So you never have to sort inputs by hand.

Case E — both inputs zero, $g cd (0, 0)$ . This is the one genuinely undefined corner. Every integer divides $0$ , so there is no greatest common divisor — the set of common divisors is unbounded. By the convention $g cd (0, 0) = 0$ , but no Bézout recipe $0 \cdot x + 0 \cdot y = 0$ is meaningful (any $x, y$ works). Exclude this input: require that $a$ and $b$ are not both zero before running the algorithm.

WHY show all five? If you only ever practise the "nice" case, the $q = 0$ swap, the instant- $0$ remainder, or the $(0, 0)$ trap look like bugs. They aren't — the same recurrence handles A–D with zero special-casing, and E is guarded out at the door.

PICTURE. Five small panels, one per case, each showing the (very short) staircase and the final recipe card, with the $(0, 0)$ panel flagged as excluded.

The one-picture summary

Everything at once: the divisions on the left build the shrinking remainders; the recipe cards on the right ride along, each computed by "two positions back minus $q$ times one position back"; and at the bottom the last non-zero remainder $1$ emerges wearing its recipe $(- 4, 15)$ , giving Bézout: $56 \cdot (- 4) + 15 \cdot 15 = 1$ .

Recall Feynman: the whole walkthrough in plain words

Line-em-up two numbers, 56 and 15. Keep fitting the smaller into the bigger and looking at the crumb left over — 11, then 4, then 3, then 1, then it fits perfectly and there's no crumb. The last real crumb, 1, is the gcd.

The clever extra bit: every crumb secretly remembers "I'm made of this many 56s and this many 15s." The first crumb 11 is "one 56 take away three 15s." Because each new crumb is built by the same subtraction from the two crumbs before it, its recipe is built by the very same subtraction on their recipes. So when the final crumb 1 shows up, it already knows it's " $- 4$ copies of 56 plus $15$ copies of 15." That's $56 \cdot (- 4) + 15 \cdot 15 = 1$ — which is why one line of arithmetic gives you inverses, Diophantine solutions, and RSA keys.

Connections

Euclidean Algorithm — the plain version we extended in Step 2
Bézout's Identity — the $a x + b y = g cd$ result the recipes prove
Modular Multiplicative Inverse — Case C: the coefficient $x$ is the inverse
Linear Diophantine Equations — scale the recipe to solve $a x + b y = c$
Chinese Remainder Theorem — glues congruences using these inverses
RSA Algorithm — private key $d$ from $e d \equiv 1$