Extended Euclidean algorithm: Foundations — Maths deep dive

Before we can even read the parent note, we need to earn each piece of its vocabulary. We go one symbol at a time, and nothing is used before it is drawn.

0. Two operators we lean on: $+$ (add) and $<, >$ (order)

The picture: everything is just which side of the other a point sits on the same line we draw next. We name these now because every later rule ("the remainder satisfies $0 \leq r < b$ ") is spoken in this language.

1. Whole numbers and the number line

The picture is a number line: evenly spaced ticks stretching left and right forever. Positive numbers step right, negative numbers step left, zero sits in the middle.

Why the topic needs it. Everything in this chapter — remainders, coefficients, gcds — lives on this line. When we later write $x = - 4$ , that is just "walk 4 steps left of zero". The letters $a, b, x, y$ that fill the parent note are all integers; they are all just chosen points on this line.

2. Letters standing for numbers: $a$ , $b$ , $x$ , $y$

The picture: think of $a$ and $b$ as two labelled tokens sitting on the number line. In the parent note:

$a$ and $b$ are the two numbers we start with (e.g. $56$ and $15$ ).
$x$ and $y$ are the two answers we are hunting for — how many copies of $a$ and of $b$ to combine.

Why the topic needs it. The whole point is a general recipe that works for any starting pair. Naming the pair $a, b$ lets us state one formula instead of redoing arithmetic for every example.

3. Multiplication as repeated stacking, and $a x + b y$

The picture: a stack of equal-length jumps along the number line. $3 a$ is three jumps of length $a$ to the right; $- 2 a$ is two jumps of length $a$ to the left.

Why the topic needs it. The star formula the parent note chases — a linear combination that equals the gcd (defined next in §4) — is exactly this shape $a x + b y$ . The entire algorithm is a machine for finding the two coefficients $x$ and $y$ . If "linear combination" is fuzzy, the goal is invisible.

4. Divides, common divisor, and $g cd$

The picture: measure two sticks of length $a$ and $b$ with the same ruler. A common divisor is any ruler-spacing that fits both sticks a whole number of times. The gcd is the longest such spacing — the biggest tile that paves both sticks perfectly.

Why the topic needs it. $g cd (a, b)$ is the target the algorithm computes and the right-hand side of Bézout's identity. See Euclidean Algorithm for the plain version that finds only this number.

5. Quotient and remainder: $a = q b + r$

This is the heartbeat of the whole algorithm, so we build it carefully.

The picture: pour $a$ into buckets each holding $b$ . You fill $q$ full buckets; the puddle that can't fill another bucket is $r$ .

Why the topic needs it. Every single row of the Extended Euclidean table is one division equation. The subscripted symbols $r_{1}, r_{2}, \dots$ and $q_{1}, q_{2}, \dots$ below are just this same step, repeated.

6. Subscripts, the remainder chain, and the coefficient sequences

The picture: a row of numbered lockers. $r_{i}$ is "whatever is in locker $i$ ". $r_{i - 1}$ is "the locker just before $i$ "; $r_{i - 2}$ is "two lockers before $i$ ".

Where the chain starts. We seed the two lockers before any division happens: $r_{0} = a, r_{1} = b .$ Then each new locker is the remainder of dividing the two before it, using §5's equation $r_{i - 2} = q_{i} r_{i - 1} + r_{i}$ , i.e. $r_{i} = r_{i - 2} - q_{i} r_{i - 1} .$

Now the two coefficient sequences. For each locker we also track how that remainder is built from $a$ and $b$ . We define two number sequences $x_{i}$ and $y_{i}$ by the requirement $r_{i} = x_{i} a + y_{i} b for every i .$ Their starting values fall straight out of the seeds:

$r_{0} = a = 1 \cdot a + 0 \cdot b ⟹ (x_{0}, y_{0}) = (1, 0)$ .
$r_{1} = b = 0 \cdot a + 1 \cdot b ⟹ (x_{1}, y_{1}) = (0, 1)$ .

Why the recurrence follows. Each new remainder is literally the same subtraction $r_{i - 2} - q_{i} r_{i - 1}$ we do on the numbers — we just perform it on their $a, b$ recipes instead. The coefficients obey the exact same "two-lockers-ago minus $q_{i}$ times one-locker-ago" rule because that is the only operation happening. That is the whole engine of the Extended algorithm.

Why the topic needs it. The parent note's recurrence $x_{i} = x_{i - 2} - q_{i} x_{i - 1}$ is now grounded: you know what $x_{i}$ is (the $a$ -coefficient of locker $i$ ), where it starts ( $x_{0} = 1, x_{1} = 0$ ), and why the formula holds (it inherits the remainder subtraction).

7. Congruence and $(mod m)$ (for the applications)

The picture: a clock with $m$ marks. Walking $a$ steps and walking $c$ steps land you on the same mark. On a $12$ -hour clock, $13 \equiv 1 (mod 12)$ .

Why the topic needs it. The parent note's applications — Modular Multiplicative Inverse, RSA Algorithm — live on this clock. From $a x + m y = 1$ you read $a x \equiv 1 (mod m)$ : on the mod- $m$ clock, the $m y$ term wraps all the way around and vanishes, leaving $a x$ landing on mark $1$ . That is why the coefficient $x$ is the inverse.

How these foundations feed the topic

Read top to bottom: add/order and the number line give us letters and linear combinations and the gcd; division-with-remainder plus subscripts give us the plain Euclidean algorithm; tracking coefficient sequences through it gives the extended version, which produces Bézout's identity, which powers the mod- $m$ applications.

Equipment checklist

Cover the right side and answer each before opening the parent note.

What does

a < b

mean on the number line?

a

sits to the left of

b

What is an integer, in one phrase?

Any whole number — positive, negative, or zero — with no fractional part.

What does

d ∣ n

mean in plain words?

Copies of

d

laid end to end hit

n

exactly, no leftover.

What is

g cd (a, b)

, and what is

g cd (a, 0)

The largest number dividing both

a

and

b

(taken nonnegative);

g cd (a, 0) = ∣ a ∣

What is a linear combination of

a

and

b

Any number of the form

a x + b y

using integer coefficients

x, y

a = q b + r

, what are

q

and

r

, what constraint does

r

obey, and what may

b

never be?

q

is how many whole copies of

b

fit in

a

;

r

is the leftover with

0 \leq r < b

;

b

may never be

0

r_{2}

equal to

2 \times r

No — the subscript

2

is an address ("second remainder"), not a multiplier.

What are the seed values

r_{0}, r_{1}

and the coefficient seeds

(x_{0}, y_{0}), (x_{1}, y_{1})

r_{0} = a

with

(1, 0)

, and

r_{1} = b

with

(0, 1)

Why does

x_{i} = x_{i - 2} - q_{i} x_{i - 1}

hold?

Because

r_{i} = r_{i - 2} - q_{i} r_{i - 1}

, and substituting each remainder's

a, b

recipe pushes that same subtraction onto the coefficients.

Why does the remainder chain eventually reach

0

Because each remainder is strictly smaller than the previous (

0 \leq r < b

), so they shrink and must hit

0

What does

a x \equiv 1 (mod m)

say on a clock?

On the

m

-mark clock,

x

copies of

a

land exactly on mark

1

Connections

Euclidean Algorithm — the plain gcd-finder these foundations lead into
Bézout's Identity — the equation $a x + b y = g cd (a, b)$ all this vocabulary lets you read
Modular Multiplicative Inverse — needs the congruence and gcd pieces from §4 and §7
Linear Diophantine Equations — built on linear combinations from §3
Chinese Remainder Theorem — layers congruences from §7
RSA Algorithm — uses inverses mod $m$ from §7

locker $i$	$r_{i - 2}$	$r_{i - 1}$	$q_{i}$	$r_{i} = r_{i - 2} - q_{i} r_{i - 1}$
$r_{0}$	—	—	—	$56$ (seeded $= a$ )
$r_{1}$	—	—	—	$15$ (seeded $= b$ )
$r_{2}$	$56$	$15$	$3$	$56 - 3 \cdot 15 = 11$
$r_{3}$	$15$	$11$	$1$	$15 - 1 \cdot 11 = 4$
$r_{4}$	$11$	$4$	$2$	$11 - 2 \cdot 4 = 3$
$r_{5}$	$4$	$3$	$1$	$4 - 1 \cdot 3 = 1$
$r_{6}$	$3$	$1$	$3$	$3 - 3 \cdot 1 = 0$