Extended Euclidean algorithm

Intuition The Reverse-Engineering View

The regular Euclidean algorithm finds $\gcd(a,b)$ by repeatedly removing the smaller from the larger. The Extended version runs the same process but keeps track of "how we built the gcd from $a$ and $b$ " — it discovers integers $x, y$ such that $ax + by = \gcd(a,b)$ . This is Bézout's identity, and it's the foundation of modular inverses, RSA, and solving linear Diophantine equations.

Why it works: At each step of Euclid's algorithm, we write $r_i = r_{i-2} - q_i \cdot r_{i-1}$ . Since the first two remainders are $a$ and $b$ , every remainder can be expressed as a linear combination of $a$ and $b$ . The Extended algorithm just tracks the coefficients.

Derivation from First Principles

How the Regular Algorithm Works

Start with $a \geq b > 0$ . The Euclidean algorithm produces a sequence:

\begin{align} a &= q_1 b + r_1 \quad (0 \leq r_1 < b) \\ b &= q_2 r_1 + r_2 \quad (0 \leq r_2 < r_1) \\ r_1 &= q_3 r_2 + r_3 \\ &\vdots \\ r_{n-2} &= q_n r_{n-1} + r_n \\ r_{n-1} &= q_{n+1} r_n + 0 \end{align}

The last non-zero remainder $r_n$ is $\gcd(a, b)$ .

Tracking Coefficients Backwards

From the second-to-last equation: $r_n = r_{n-2} - q_n r_{n-1}$ .

Substitute the expression for $r_{n-1}$ from the line above, then $r_{n-2}$ , and so on, all the way back to $a$ and $b$ . This substitution reveals $r_n = x \cdot a + y \cdot b$ for some integers $x, y$ .

The Forward (Efficient) Method

Instead of backtracking, maintain coefficients $(x_i, y_i)$ at each step such that $r_i = x_i a + y_i b$ .

Base cases:

$r_0 = a = 1\cdot a + 0 \cdot b \implies (x_0, y_0) = (1, 0)$
$r_1 = b = 0 \cdot a + 1 \cdot b \implies (x_1, y_1) = (0, 1)$

Recurrence: From $r_i = r_{i-2} - q_i r_{i-1}$ , we have: $r_i = (x_{i-2} a + y_{i-2} b) - q_i (x_{i-1} a + y_{i-1} b)$ $= (x_{i-2} - q_i x_{i-1}) a + (y_{i-2} - q_i y_{i-1}) b$

Why this step? Each remainder is a linear combination of the previous two. If we know how to write the previous two in terms of $a$ and $b$ , we can write the new one the same way.

Worked Examples

Step	$r_{i-2}$	$r_{i-1}$	$q_i$	$r_i$	$x_{i-2}$	$x_{i-1}$	$x_i = x_{i-2} - q_i x_{i-1}$	$y_{i-2}$	$y_{i-1}$	$y_i = y_{i-2} - q_i y_{i-1}$
0	—	—	—	56	1	—	—	0	—	—
1	—	—	—	15	—	0	—	—	1	—
2	56	15	3	11	1	0	$1 - 3 \cdot 0 = 1$	0	1	$0 - 3 \cdot 1 = -3$
3	15	11	1	4	0	1	$0 - 1 \cdot 1 = -1$	1	-3	$1 - 1 \cdot (-3) = 4$
4	11	4	2	3	1	-1	$1 - 2 \cdot (-1) = 3$	-3	4	$-3 - 2 \cdot 4 = -11$
5	4	3	1	1	-1	3	$-1 - 1 \cdot 3 = -4$	4	-11	$4 - 1 \cdot (-11) = 15$
6	3	1	3	0	—	—	—	—	—	—

Result: $\gcd(56, 15) = 1$ , with $x = -4$ , $y = 15$ .

Verification: $56 \cdot (-4) + 15 \cdot 15 = -224 + 225 = 1$ . ✓

Why this step? Each row computes the new remainder and updates coefficients using the recurrence. When $r_i = 0$ , the previous row gives the answer.

Step	$r_{i-2}$	$r_{i-1}$	$q_i$	$r_i$	$x_i$	$y_i$
0	—	—	—	240	1	0
1	—	—	—	46	0	1
2	240	46	5	10	1 - 5·0 = 1	0 - 5·1 = -5
3	46	10	4	6	0 - 4·1 = -4	1 - 4·(-5) = 21
4	10	6	1	4	1 - 1·(-4) = 5	-5 - 1·21 = -26
5	6	4	1	2	-4 - 1·5 = -9	21 - 1·(-26) = 47
6	4	2	2	0	—	—

Result: $\gcd(240, 46) = 2$ , with $x = -9$ , $y = 47$ .

Check: $240 \cdot (-9) + 46 \cdot 47 = -2160 + 2162 = 2$ . ✓

Common Mistakes

Applications

Modular Inverse: To find $a^{-1} \pmod{m}$ (when $\gcd(a, m) = 1$ ), run Extended Euclidean on $a$ and $m$ . The coefficient $x$ satisfying $ax + my = 1$ is the inverse: $ax \equiv 1 \pmod{m}$ .
Linear Diophantine Equations: To solve $ax + by = c$ , first find $\gcd(a,b)$ . If $c$ is not a multiple of $\gcd(a,b)$ , no solution exists. Otherwise, scale the Bézout coefficients: if $ax_0 + by_0 = \gcd(a,b)$ , then $x = x_0 \cdot (c / \gcd(a,b))$ and $y = y_0 \cdot (c / \gcd(a,b))$ is a particular solution.
RSA Cryptography: Computing the private key $d$ such that $ed \equiv 1 \pmod{\phi(n)}$ uses the Extended Euclidean Algorithm.

Diagram

Recall Feynman: Explain to a 12-year-old

Imagine you have two piles of coins, say 56 and 15. The regular Euclidean algorithm is like repeatedly removing the smaller pile from the larger until you're left with the biggest pile size that divides both (the gcd).

Now, the Extended version asks: "Can I combine the original two pile sizes using addition and subtraction to build exactly this gcd?" The answer is always yes! The algorithm keeps a running tally: "So far, this remainder is made of __ copies of the first pile and ___ copies of the second pile (where negative means we're subtracting)."

At the end, you know exactly how many of each original pile you need to add/subtract to get the gcd. That's the magic formula $ax + by = \gcd(a,b)$ and it's used everywhere in number theory!

Connections

Euclidean Algorithm — the "non-extended" version that only finds $\gcd(a,b)$
Bézout's Identity — theorem guaranteeing integer solutions $ax + by = \gcd(a,b)$
Modular Multiplicative Inverse — found using Extended Euclidean when $\gcd(a, m) = 1$
Linear Diophantine Equations — solved by scaling Bézout coefficients
Chinese Remainder Theorem — uses modular inverses in its construction
RSA Algorithm — private key calculation relies on Extended Euclidean

#flashcards/maths

What does the Extended Euclidean Algorithm compute? :: It computes $\gcd(a, b)$ and integers $x, y$ such that $ax + by = \gcd(a, b)$ (Bézout's identity).

What are the base cases for the coefficient recurrence?

(x_0, y_0) = (1, 0)

for

r_0 = a

, and

(x_1, y_1) = (0, 1)

for

r_1 = b

What is the recurrence for

x_i

in the Extended Euclidean Algorithm?

x_i = x_{i-2} - q_i \cdot x_{i-1}

, where

q_i

is the quotient at step

i

How do you find the modular inverse of $a$ modulo $m$ using Extended Euclidean? :: Run Extended Euclidean on $a$ and $m$ . If $\gcd(a, m) = 1$ , the coefficient $x$ from $ax + my = 1$ is the inverse $a^{-1} \pmod{m}$ .

When does the linear Diophantine equation

ax + by = c

have integer solutions?

If and only if

\gcd(a, b)

divides

c

If $56x + 15y = \gcd(56, 15)$ , what are $x$ and $y$ ? :: $x = -4$ , $y = 15$ , since $56(-4) + 15(15) = 1$ and $\gcd(56, 15) = 1$ .

Why do we use the second-to-last row for the gcd and coefficients?

The last remainder is always 0. The gcd is the last non-zero remainder, which appears in the second-to-last row.

What is Bézout's Identity?

For any integers

a, b

(not both zero), there exist integers

x, y

such that

ax + by = \gcd(a, b)

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Extended Euclidean Algorithm ek powerful technique hai jo tumhe sirf gcd nahi, balki ek special combination bhi deta hai: $ax + by = \gcd(a,b)$ . Matlab agar tumhare pas do numbers hain, toh yeh algorithm tumhe bata dega kitne copies first number ke aur kitne copies second number ke (addition ya subtraction ke sath) mil kar exactly gcd ban sakta hai. Yeh Bézout's identity kehlata hai aur number theory mein bahut kaam ata hai.

Algorithm simple hai — regular Euclidean algorithm ki tarah divisions karte raho, lekin sath-saath do extra columns maintain karo: $x_i$ aur $y_i$ . Har step par recurrence use karo: $x_i = x_{i-2} - q_i \cdot x_{i-1}$ (same for $y_i$ ). Base case yad rakho: pehla number $(1, 0)$ se start hota hai aur dosra $(0, 1)$ se, kyunki $a = 1 \cdot a + 0 \cdot b$ aur $b = 0 \cdot a + 1 \cdot b$ .

Iska sabse bada use modular inverse nikalne mein hota hai. Agar tumhe $a^{-1} \pmod{m}$ chahiye (cryptography aur coding theory mein zaroori), toh Extended Euclidean chala do $a$ aur $m$ par. Jo $x$ milega wahi inverse hai! Linear Diophantine equations solve karne ke liye bhi yahi method use hota hai. Basically, yeh algorithm tumhe number theory ke bahut sare problems ka direct solution de deta hai, efficiently aur exactly.

Derivation from First Principles

How the Regular Algorithm Works

Tracking Coefficients Backwards

The Forward (Efficient) Method

Worked Examples

Common Mistakes

Applications

Diagram

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Number Theory (Intermediate)

Connections