Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division

The recursion gcd(a,b) = gcd(b, a mod b) hides an invariant: the set of common divisors never changes. Starting from a naive subtraction-based method and upgrading to division, we derive Bezout's identity, the extended Euclidean algorithm, and modular inverses.

Folio Official

March 1, 2026

The Euclidean algorithm, recorded in Euclid's Elements around 300 BCE, is one of the oldest algorithms known to humanity. Yet textbooks often present it as a bare recursion – $g cd (a, b) = g cd (b, a mod b)$ – without explaining why this operation reliably produces the greatest common divisor.

1 The definition of the greatest common divisor

Definition 1 (Greatest common divisor).

For nonzero integers

a

and

b

, the greatest common divisor

g cd (a, b)

is the largest positive integer that divides both

a

and

b

Remark 2.

Intuitively,

g cd (a, b)

collects all the prime factors that

a

and

b

share. For example,

g cd (12, 18) = 6

, since

12 = 2^{2} \times 3

and

18 = 2 \times 3^{2}

, and the common part is

2 \times 3 = 6

2 The naive approach: repeated subtraction

The simplest way to compute the greatest common divisor is by repeated subtraction.

Theorem 3 (Subtraction preserves the GCD).

a > b > 0

, then

g cd (a, b) = g cd (a - b, b)

Proof.

d ∣ a

and

d ∣ b

, then

d ∣ (a - b)

. Conversely, if

d ∣ (a - b)

and

d ∣ b

, then

d ∣ a

. Thus the set of common divisors of

(a, b)

and

(a - b, b)

is the same, so their maxima coincide. □

Example 4.

Computing

g cd (48, 18)

by subtraction:

g cd (48, 18) = g cd (30, 18) = g cd (12, 18) = g cd (12, 6) = g cd (6, 6) = 6

This method is correct but slow. When $a$ and $b$ are far apart, it can require an enormous number of steps ( $g cd (1 0^{9}, 1)$ would need $1 0^{9}$ subtractions).

3 The upgrade to division: why the algorithm is fast

Instead of subtracting one copy of $b$ at a time, we subtract as many copies as possible in a single step – that is, we divide.

Theorem 5 (The core identity of the Euclidean algorithm).

a \geq b > 0

, then

g cd (a, b) = g cd (b, a mod b)

Proof.

Write

a = q b + r

with

0 \leq r < b

. If

d ∣ a

and

d ∣ b

, then

d ∣ (a - q b) = r

. Conversely, if

d ∣ b

and

d ∣ r

, then

d ∣ (q b + r) = a

. Therefore

g cd (a, b) = g cd (b, r)

. □

Remark 6.

The subtraction version reduces

a

b

in each step; the division version reduces

a

all the way to

a mod b

in a single step, effectively performing

q

subtractions at once.

Theorem 7 (Complexity).

The Euclidean algorithm runs in

O (lo g (min (a, b)))

steps.

Remark 8.

Why logarithmic? The key observation is that

a mod b < a /2

always holds. If

b \leq a /2

, then the remainder is less than

b \leq a /2

. If

b > a /2

, then

a mod b = a - b < a /2

. In either case, every two consecutive steps halve the larger argument, and the algorithm terminates in

O (lo g a)

steps.

4 Bézout's identity: the GCD as a linear combination

Theorem 9 (B\'ezout's identity).

For any integers

a

and

b

, there exist integers

x

and

y

such that

g cd (a, b) = a x + b y .

Proof.

The coefficients

x, y

can be constructed by tracing the Euclidean algorithm in reverse. In the base case,

g cd (d, 0) = d = d \cdot 1 + 0 \cdot 0

. For the recursive step, suppose

g cd (b, a mod b) = b x^{'} + (a mod b) y^{'}

. Substituting

a mod b = a - ⌊ a / b ⌋ b

gives

g cd (a, b) = a y^{'} + b (x^{'} - ⌊ a / b ⌋ y^{'})

. □

5 The extended Euclidean algorithm

The constructive proof of Béextended Euclidean algorithm.

Example 10.

We compute

g cd (111, 30)

and find integers

x, y

with

111 x + 30 y = g cd (111, 30)

$111 = 3 \times 30 + 21$
$30 = 1 \times 21 + 9$
$21 = 2 \times 9 + 3$
$9 = 3 \times 3 + 0$

g cd (111, 30) = 3

. Now we back-substitute:

$3 = 21 - 2 \times 9$
$= 21 - 2 (30 - 21) = 3 \times 21 - 2 \times 30$
$= 3 (111 - 3 \times 30) - 2 \times 30 = 3 \times 111 - 11 \times 30$

Check:

3 \times 111 - 11 \times 30 = 333 - 330 = 3

6 Computing modular inverses

Theorem 11 (Modular inverse).

g cd (a, n) = 1

, there exists an integer

x

satisfying

a x \equiv 1 (mod n)

. This

x

is called the modular inverse of

a

modulo

n

Proof.

By Bé

a x + n y = 1

for some integers

x, y

. Reducing both sides modulo

n

gives

a x \equiv 1 (mod n)

. □

Remark 12 (Modular inverses in competitive programming).

When

p

is prime and

a \neq \equiv 0 (mod p)

, we have

g cd (a, p) = 1

, so the extended Euclidean algorithm computes the inverse in

O (lo g p)

time. Compared with the alternative

a^{p - 2} mod p

(via Fermat's little theorem), the extended Euclidean algorithm has a smaller constant factor and, crucially, also works when the modulus is not prime.

7 Takeaway

The Euclidean algorithm rests on the invariant that the set of common divisors is unchanged at each step.
Upgrading subtraction to division yields an $O (lo g)$ -time algorithm.
Bé
The extended Euclidean algorithm turns this guarantee into an efficient procedure for computing modular inverses.

In the next article, we examine the "atoms" of the integers – the primes – and ask why the Fundamental Theorem of Arithmetic holds, and in what settings it fails.

Number Theory Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division

Folio Official

March 1, 2026

1 The definition of the greatest common divisor

Definition 1 (Greatest common divisor).

For nonzero integers

a

and

b

, the greatest common divisor

g cd (a, b)

is the largest positive integer that divides both

a

and

b

Remark 2.

Intuitively,

g cd (a, b)

collects all the prime factors that

a

and

b

share. For example,

g cd (12, 18) = 6

, since

12 = 2^{2} \times 3

and

18 = 2 \times 3^{2}

, and the common part is

2 \times 3 = 6

2 The naive approach: repeated subtraction

The simplest way to compute the greatest common divisor is by repeated subtraction.

Theorem 3 (Subtraction preserves the GCD).

a > b > 0

, then

g cd (a, b) = g cd (a - b, b)

Proof.

d ∣ a

and

d ∣ b

, then

d ∣ (a - b)

. Conversely, if

d ∣ (a - b)

and

d ∣ b

, then

d ∣ a

. Thus the set of common divisors of

(a, b)

and

(a - b, b)

is the same, so their maxima coincide. □

Example 4.

Computing

g cd (48, 18)

by subtraction:

g cd (48, 18) = g cd (30, 18) = g cd (12, 18) = g cd (12, 6) = g cd (6, 6) = 6

This method is correct but slow. When $a$ and $b$ are far apart, it can require an enormous number of steps ( $g cd (1 0^{9}, 1)$ would need $1 0^{9}$ subtractions).

3 The upgrade to division: why the algorithm is fast

Instead of subtracting one copy of $b$ at a time, we subtract as many copies as possible in a single step – that is, we divide.

Theorem 5 (The core identity of the Euclidean algorithm).

a \geq b > 0

, then

g cd (a, b) = g cd (b, a mod b)

Proof.

Write

a = q b + r

with

0 \leq r < b

. If

d ∣ a

and

d ∣ b

, then

d ∣ (a - q b) = r

. Conversely, if

d ∣ b

and

d ∣ r

, then

d ∣ (q b + r) = a

. Therefore

g cd (a, b) = g cd (b, r)

. □

Remark 6.

The subtraction version reduces

a

b

in each step; the division version reduces

a

all the way to

a mod b

in a single step, effectively performing

q

subtractions at once.

Theorem 7 (Complexity).

The Euclidean algorithm runs in

O (lo g (min (a, b)))

steps.

Remark 8.

Why logarithmic? The key observation is that

a mod b < a /2

always holds. If

b \leq a /2

, then the remainder is less than

b \leq a /2

. If

b > a /2

, then

a mod b = a - b < a /2

. In either case, every two consecutive steps halve the larger argument, and the algorithm terminates in

O (lo g a)

steps.

4 Bézout's identity: the GCD as a linear combination

Theorem 9 (B\'ezout's identity).

For any integers

a

and

b

, there exist integers

x

and

y

such that

g cd (a, b) = a x + b y .

Proof.

The coefficients

x, y

can be constructed by tracing the Euclidean algorithm in reverse. In the base case,

g cd (d, 0) = d = d \cdot 1 + 0 \cdot 0

. For the recursive step, suppose

g cd (b, a mod b) = b x^{'} + (a mod b) y^{'}

. Substituting

a mod b = a - ⌊ a / b ⌋ b

gives

g cd (a, b) = a y^{'} + b (x^{'} - ⌊ a / b ⌋ y^{'})

. □

5 The extended Euclidean algorithm

The constructive proof of Béextended Euclidean algorithm.

Example 10.

We compute

g cd (111, 30)

and find integers

x, y

with

111 x + 30 y = g cd (111, 30)

$111 = 3 \times 30 + 21$
$30 = 1 \times 21 + 9$
$21 = 2 \times 9 + 3$
$9 = 3 \times 3 + 0$

g cd (111, 30) = 3

. Now we back-substitute:

$3 = 21 - 2 \times 9$
$= 21 - 2 (30 - 21) = 3 \times 21 - 2 \times 30$
$= 3 (111 - 3 \times 30) - 2 \times 30 = 3 \times 111 - 11 \times 30$

Check:

3 \times 111 - 11 \times 30 = 333 - 330 = 3

6 Computing modular inverses

Theorem 11 (Modular inverse).

g cd (a, n) = 1

, there exists an integer

x

satisfying

a x \equiv 1 (mod n)

. This

x

is called the modular inverse of

a

modulo

n

Proof.

By Bé

a x + n y = 1

for some integers

x, y

. Reducing both sides modulo

n

gives

a x \equiv 1 (mod n)

. □

Remark 12 (Modular inverses in competitive programming).

When

p

is prime and

a \neq \equiv 0 (mod p)

, we have

g cd (a, p) = 1

, so the extended Euclidean algorithm computes the inverse in

O (lo g p)

time. Compared with the alternative

a^{p - 2} mod p

(via Fermat's little theorem), the extended Euclidean algorithm has a smaller constant factor and, crucially, also works when the modulus is not prime.

7 Takeaway

The Euclidean algorithm rests on the invariant that the set of common divisors is unchanged at each step.
Upgrading subtraction to division yields an $O (lo g)$ -time algorithm.
Bé
The extended Euclidean algorithm turns this guarantee into an efficient procedure for computing modular inverses.

In the next article, we examine the "atoms" of the integers – the primes – and ask why the Fundamental Theorem of Arithmetic holds, and in what settings it fails.

Number Theory Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division

1 The definition of the greatest common divisor

2 The naive approach: repeated subtraction

3 The upgrade to division: why the algorithm is fast

4 Bézout's identity: the GCD as a linear combination

5 The extended Euclidean algorithm

6 Computing modular inverses

7 Takeaway

Share your expertise with the world

More from Folio Official

Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says

The Chinese Remainder Theorem: why simultaneous congruences can be merged

What does it mean to "divide evenly"? Why number theory begins with mod

Number theory meets cryptography: why RSA works and what makes it secure

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division

1 The definition of the greatest common divisor

2 The naive approach: repeated subtraction

3 The upgrade to division: why the algorithm is fast

4 Bézout's identity: the GCD as a linear combination

5 The extended Euclidean algorithm

6 Computing modular inverses

7 Takeaway

Share your expertise with the world

More from Folio Official

Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says

The Chinese Remainder Theorem: why simultaneous congruences can be merged

What does it mean to "divide evenly"? Why number theory begins with mod

Number theory meets cryptography: why RSA works and what makes it secure