Extended Euclidean algorithm: Worked examples

This page is a drill. The parent note built the machine — the recurrence $x_{i} = x_{i - 2} - q_{i} x_{i - 1}$ that walks Bézout coefficients forward. Here we throw every kind of input at that machine and watch it survive: big vs small, coprime vs not, a zero input, negative numbers, a modular-inverse job, a Diophantine word problem, and one exam trap. Miss none of these and no problem can surprise you.

Everything below reuses only two facts from the parent:

The remainder $r_{i}$ is what's left after you fit $r_{i - 1}$ into $r_{i - 2}$ as many whole times as possible; that count is the quotient $q_{i}$ .
We keep two side-columns $x_{i}, y_{i}$ so that at every row $r_{i} = x_{i} a + y_{i} b$ . They start at $(1, 0)$ for $a$ and $(0, 1)$ for $b$ .

The scenario matrix

Definition The cases this topic can throw at you

Cell	Scenario	Why it's different	Example
A	$g cd = 1$ (coprime)	Bézout gives $\dots = 1$ , so $x$ is a modular inverse	Ex 1
B	$g cd > 1$ (share a factor)	RHS is the shared factor, not 1	Ex 2
C	One number divides the other	Algorithm halts after one step	Ex 3
D	A zero input, $g cd (a, 0)$	Degenerate — no division happens	Ex 4
E	Negative input	Fix signs, then run as usual	Ex 5
F	Modular inverse $a^{- 1} mod m$	Read off $x$ , then push it into range $[0, m)$	Ex 6
G	Diophantine word problem $a x + b y = c$	Scale Bézout, check $c$ divisible by gcd	Ex 7
H	No-solution Diophantine	$c$ not a multiple of gcd → stop	Ex 8
I	Exam twist: which row holds the answer?	Off-by-one row trap	Ex 9

We'll cover each cell exactly once. Read the Forecast line and guess before scrolling.

The table shape (and its two starting rows)

Every example is a small table. Each row records five things: the two remainders we're dividing, the quotient $q_{i}$ , the new remainder $r_{i}$ , and the two updated coefficients $x_{i}, y_{i}$ . The engine of the whole table is:

$r_{i} = r_{i - 2} - q_{i} r_{i - 1}, x_{i} = x_{i - 2} - q_{i} x_{i - 1}, y_{i} = y_{i - 2} - q_{i} y_{i - 1} .$

But this recurrence needs two rows to start from — you can't take "two behind" and "one behind" from nothing. Those two starter rows are fixed once and for all:

Let's read the figure with Example 1's first computed row ( $i = 2$ , from $g cd (101, 40)$ ). The new tile $x_{2}$ (lavender) is built from $x_{0} = 1$ (mint, two behind) minus $q_{2} = 2$ copies of $x_{1} = 0$ (butter, one behind): $x_{2} = 1 - 2 \cdot 0 = 1$ . That is exactly the arrow picture — carry the far tile down, then subtract $q_{i}$ of the near tile. Every example below is just this move, over and over.

Cell A — coprime numbers ( $g cd = 1$ )

Worked example Example 1 —

$g cd (101, 40)$ Forecast: these two share no factor (101 is prime), so the RHS will be $1$ . Guess: will $x$ be positive or negative?

Base rows: $r_{0} = 101, (x_{0}, y_{0}) = (1, 0)$ and $r_{1} = 40, (x_{1}, y_{1}) = (0, 1)$ .

Step 1. Divide: $101 = 2 \cdot 40 + 21$ , so $q_{2} = 2, r_{2} = 21$ . Update: $x_{2} = x_{0} - q_{2} x_{1} = 1 - 2 \cdot 0 = 1$ , $y_{2} = y_{0} - q_{2} y_{1} = 0 - 2 \cdot 1 = - 2$ . Why this step? The Euclidean core strips the smaller number out of the larger as many whole times as possible; the coefficient update carries $x_{0}$ down and subtracts $q_{2}$ copies of $x_{1}$ , exactly the figure's move.

Step 2. $40 = 1 \cdot 21 + 19$ : $q_{3} = 1, r_{3} = 19$ . $x_{3} = x_{1} - q_{3} x_{2} = 0 - 1 \cdot 1 = - 1$ , $y_{3} = y_{1} - q_{3} y_{2} = 1 - 1 \cdot (- 2) = 3$ . Why this step? Now the roles shift down: $21$ becomes the divisor, and the recurrence reaches back to rows $1$ and $2$ .

Step 3. $21 = 1 \cdot 19 + 2$ : $q_{4} = 1, r_{4} = 2$ . $x_{4} = x_{2} - q_{4} x_{3} = 1 - 1 \cdot (- 1) = 2$ , $y_{4} = y_{2} - q_{4} y_{3} = - 2 - 1 \cdot 3 = - 5$ . Why this step? Same recurrence, one row further along — $x_{4}$ is built from the two behind ( $x_{2} = 1$ ) minus $q_{4}$ copies of the one behind ( $x_{3} = - 1$ ), giving $1 - (- 1) = 2$ .

Step 4. $19 = 9 \cdot 2 + 1$ : $q_{5} = 9, r_{5} = 1$ . $x_{5} = x_{3} - q_{5} x_{4} = - 1 - 9 \cdot 2 = - 19$ , $y_{5} = y_{3} - q_{5} y_{4} = 3 - 9 \cdot (- 5) = 48$ . Why this step? Remainder is now $1$ — as small as a positive remainder can be for coprime inputs — so we are almost done.

Step 5. $2 = 2 \cdot 1 + 0$ : remainder hits $0$ . Stop. The last non-zero remainder is $1$ , in the row with $(x, y) = (- 19, 48)$ .

Verify: $101 \cdot (- 19) + 40 \cdot 48 = - 1919 + 1920 = 1.$ ✓ Bézout holds and $g cd = 1$ — coprime confirmed.

Cell B — a shared factor ( $g cd > 1$ )

Worked example Example 2 —

$g cd (84, 30)$ Forecast: both even, both divisible by 3, so the gcd is at least 6. The RHS of Bézout will be that gcd, not 1.

Base rows: $r_{0} = 84, (x_{0}, y_{0}) = (1, 0)$ and $r_{1} = 30, (x_{1}, y_{1}) = (0, 1)$ .

Step 1. $84 = 2 \cdot 30 + 24$ : $q_{2} = 2$ . $x_{2} = x_{0} - q_{2} x_{1} = 1 - 2 \cdot 0 = 1$ , $y_{2} = y_{0} - q_{2} y_{1} = 0 - 2 \cdot 1 = - 2$ . Why this step? Fit $30$ into $84$ twice with $24$ left over; the coefficients carry row $0$ down and subtract $2$ copies of row $1$ — the same figure move as always.

Step 2. $30 = 1 \cdot 24 + 6$ : $q_{3} = 1$ . $x_{3} = x_{1} - q_{3} x_{2} = 0 - 1 \cdot 1 = - 1$ , $y_{3} = y_{1} - q_{3} y_{2} = 1 - 1 \cdot (- 2) = 3$ . Why this step? The divisor role drops to $24$ ; the recurrence now reaches back to rows $1$ and $2$ , so $y_{3} = 1 - 1 \cdot (- 2) = 3$ (watch the double negative).

Step 3. $24 = 4 \cdot 6 + 0$ : remainder $0$ . Stop. Last non-zero remainder $= 6$ , coefficients $(- 1, 3)$ . Why this step? The moment we hit $0$ , the row above carries the gcd and its coefficients.

Verify: $84 \cdot (- 1) + 30 \cdot 3 = - 84 + 90 = 6 = g cd (84, 30) .$ ✓

Cell C — one number divides the other

Cell D — a zero input (degenerate)

Worked example Example 4 —

$g cd (0, 7)$ and $g cd (7, 0)$ Forecast: you can't divide by zero, but you can divide zero by something. What is the gcd of $0$ and $7$ ? Anything divides $0$ , so the biggest divider shared with $7$ is $7$ itself.

Step 1. For $g cd (7, 0)$ : by definition $g cd (a, 0) = ∣ a ∣$ . No division runs. Bézout: $7 = 1 \cdot 7 + 0 \cdot 0$ , so $(x, y) = (1, 0)$ . Why this step? The base row already is the answer — the second remainder is $0$ , so we stop before any quotient.

Step 2. For $g cd (0, 7)$ : by the same definition $g cd (0, 7) = 7$ , realised by the combination $0 \cdot 0 + 1 \cdot 7 = 7$ , giving $(x, y) = (0, 1)$ . Why this step? No division happens here either; we just name the combination that produces $7$ from the inputs $0$ and $7$ .

Verify: $7 \cdot 1 + 0 \cdot 0 = 7$ ✓ and $0 \cdot 0 + 7 \cdot 1 = 7$ ✓. Both degenerate cases return $7$ without a single quotient computed.

Cell E — a negative input

Worked example Example 5 — solve

$g cd (- 56, 15)$ and its Bézout pair Forecast: gcd is always taken as positive, so this equals $g cd (56, 15) = 1$ . Only the coefficient signs will differ.

Step 1. Run Extended Euclidean on the absolute values $56$ and $15$ . Base rows $r_{0} = 56, (1, 0)$ and $r_{1} = 15, (0, 1)$ .

$56 = 3 \cdot 15 + 11$ : $q_{2} = 3$ . $x_{2} = 1 - 3 \cdot 0 = 1$ , $y_{2} = 0 - 3 \cdot 1 = - 3$ .
$15 = 1 \cdot 11 + 4$ : $q_{3} = 1$ . $x_{3} = 0 - 1 \cdot 1 = - 1$ , $y_{3} = 1 - 1 \cdot (- 3) = 4$ .
$11 = 2 \cdot 4 + 3$ : $q_{4} = 2$ . $x_{4} = 1 - 2 \cdot (- 1) = 3$ , $y_{4} = - 3 - 2 \cdot 4 = - 11$ .
$4 = 1 \cdot 3 + 1$ : $q_{5} = 1$ . $x_{5} = - 1 - 1 \cdot 3 = - 4$ , $y_{5} = 4 - 1 \cdot (- 11) = 15$ .
$3 = 3 \cdot 1 + 0$ : stop. Last non-zero remainder $= 1$ with $(x, y) = (- 4, 15)$ .

So $56 \cdot (- 4) + 15 \cdot 15 = 1$ . Why this step? The algorithm's division steps need non-negative remainders, so we work with $∣ - 56 ∣ = 56$ and derive the pair honestly before dealing with the sign.

Step 2. Put the minus back. We want $(- 56) x^{'} + 15 y^{'} = 1$ . Since $56 \cdot (- 4) = (- 56) \cdot (+ 4)$ , take $x^{'} = + 4$ , $y^{'} = 15$ . Why this step? Replacing $a \to - a$ just negates the coefficient sitting on $a$ ; leave $y$ alone.

Verify: $(- 56) \cdot 4 + 15 \cdot 15 = - 224 + 225 = 1.$ ✓ Same gcd, mirrored $x$ .

Cell F — modular inverse

Cell G — Diophantine word problem

Worked example Example 7 — making exact change

Statement. You have unlimited stamps worth 7¢ and 11¢. Can you owe/pay so that the net is exactly 1¢, i.e. solve $7 x + 11 y = 1$ (negative means "give back")? Find one integer solution. Forecast: $7$ and $11$ are both prime and different, so $g cd = 1$ , which divides $1$ — a solution must exist.

Step 1. The recurrence assumes the leading number is $\geq$ the second, so put $a = 11, b = 7$ . Base rows $r_{0} = 11, (x_{0}, y_{0}) = (1, 0)$ and $r_{1} = 7, (x_{1}, y_{1}) = (0, 1)$ . Why this step? Swapping keeps every quotient non-negative so the division steps behave.

Step 2. $11 = 1 \cdot 7 + 4$ : $q_{2} = 1$ . $x_{2} = x_{0} - q_{2} x_{1} = 1 - 1 \cdot 0 = 1$ , $y_{2} = y_{0} - q_{2} y_{1} = 0 - 1 \cdot 1 = - 1$ . Why this step? Carry row $0$ down, subtract $1$ copy of row $1$ — the figure move again.

Step 3. $7 = 1 \cdot 4 + 3$ : $q_{3} = 1$ . $x_{3} = x_{1} - q_{3} x_{2} = 0 - 1 \cdot 1 = - 1$ , $y_{3} = y_{1} - q_{3} y_{2} = 1 - 1 \cdot (- 1) = 2$ . Why this step? The divisor drops to $4$ ; the recurrence now reaches back to rows $1$ and $2$ .

Step 4. $4 = 1 \cdot 3 + 1$ : $q_{4} = 1$ . $x_{4} = x_{2} - q_{4} x_{3} = 1 - 1 \cdot (- 1) = 2$ , $y_{4} = y_{2} - q_{4} y_{3} = - 1 - 1 \cdot 2 = - 3$ . Why this step? Remainder is now $1$ ; the next division will zero out, so this row holds the answer.

Step 5. $3 = 3 \cdot 1 + 0$ : stop. So (with $a = 11, b = 7$ ) $11 \cdot 2 + 7 \cdot (- 3) = 1$ .

Step 6. Translate back to $7 x + 11 y = 1$ : the same equation reads $7 \cdot (- 3) + 11 \cdot 2 = 1$ , so $x = - 3, y = 2$ . Because $c = 1 = g cd$ , no scaling is needed. Why this step? We only swapped the names $a, b$ ; undoing the swap just relabels which coefficient sits on the $7$ .

Verify: $7 \cdot (- 3) + 11 \cdot 2 = - 21 + 22 = 1.$ ✓ (full family: $x = - 3 + 11 t, y = 2 - 7 t$ .)

Cell H — no-solution Diophantine

Cell I — exam twist: which row holds the answer?

Worked example Example 9 — the off-by-one trap on

$g cd (240, 46)$ Statement. A student runs Extended Euclidean on $240$ and $46$ and asks: "which row do I read the coefficients from — the last one, where $r = 0$ ?" Work the table and settle it. Forecast: the last row has $r_{i} = 0$ and no valid coefficients. The gcd lives in the second-to-last row.

Step 1. Build the table (base rows $r_{0} = 240, (1, 0)$ and $r_{1} = 46, (0, 1)$ ):

$240 = 5 \cdot 46 + 10$ : $q = 5$ . $x = 1 - 5 \cdot 0 = 1, y = 0 - 5 \cdot 1 = - 5$ . ( $r = 10$ )
$46 = 4 \cdot 10 + 6$ : $q = 4$ . $x = 0 - 4 \cdot 1 = - 4, y = 1 - 4 \cdot (- 5) = 21$ . ( $r = 6$ )
$10 = 1 \cdot 6 + 4$ : $q = 1$ . $x = 1 - 1 \cdot (- 4) = 5, y = - 5 - 1 \cdot 21 = - 26$ . ( $r = 4$ )
$6 = 1 \cdot 4 + 2$ : $q = 1$ . $x = - 4 - 1 \cdot 5 = - 9, y = 21 - 1 \cdot (- 26) = 47$ . ( $r = 2$ )
$4 = 2 \cdot 2 + 0$ : remainder $0$ , dashes for coefficients. ( $r = 0$ ) Why this step? Running the full table makes the trap visible: the $r = 2$ row carries $(x, y) = (- 9, 47)$ ; the final $r = 0$ row carries nothing usable.

Step 2. Report the gcd from the last non-zero remainder: $g cd = 2$ with $(x, y) = (- 9, 47)$ — from the $r = 2$ row, never the $r = 0$ row. Why this step? The recurrence runs one step past the gcd to confirm the remainder truly reaches $0$ ; that final row is bookkeeping, not the answer.

Verify: $240 \cdot (- 9) + 46 \cdot 47 = - 2160 + 2162 = 2 = g cd (240, 46) .$ ✓ Correct row, correct gcd.

Recall

Recall Which cell forces you to

stop before computing coefficients? Cell H (no solution) ::: If $g cd (a, b) ∤ c$ in a Diophantine problem, you halt right after the divisibility test — no Bézout coefficients are needed.

Recall What is

$g cd (a, 0)$ and its Bézout pair? $g cd (a, 0) = ∣ a ∣$ , achieved by $a \cdot 1 + 0 \cdot 0 = a$ ::: the base row is already the answer; no division runs.

Recall What are the two base rows every table starts from?

$r_{0} = a$ with $(x_{0}, y_{0}) = (1, 0)$ and $r_{1} = b$ with $(x_{1}, y_{1}) = (0, 1)$ ::: identity coordinates saying " $a$ is one $a$ " and " $b$ is one $b$ ".

Recall Why is the answer in the second-to-last row, never the last?

The last row's remainder is $0$ ::: the gcd is the last non-zero remainder, which sits one row up with its coefficients.

Recall How does a negative input

$a \to - a$ change the Bézout pair? It negates $x$ (the coefficient on $a$ ) and leaves $y$ unchanged ::: because $(- a) (- x) = a x$ .

Connections

Extended Euclidean Algorithm — the parent machine every example here drives
Euclidean Algorithm — the plain gcd loop underneath every row
Bézout's Identity — guarantees the $a x + b y = g cd$ we keep verifying
Modular Multiplicative Inverse — Cell F reads $x$ straight off the table
Linear Diophantine Equations — Cells G and H are its solvable / unsolvable faces
Chinese Remainder Theorem — chains several inverses like Cell F
RSA Algorithm — private key is one big Cell F computation

row $i$	remainder $r_{i}$	$x_{i}$	$y_{i}$	meaning
$0$	$a$	$1$	$0$	$a = 1 \cdot a + 0 \cdot b$
$1$	$b$	$0$	$1$	$b = 0 \cdot a + 1 \cdot b$