The Greatest Common Divisor and the Euclidean Algorithm — Algebraic Foundations of an Algorithm

We give rigorous definitions and properties of gcd and lcm, then prove the correctness and O(log min(a,b)) complexity of the Euclidean algorithm. We establish Bezout's identity, develop the extended Euclidean algorithm, and systematically solve linear congruences ax = b (mod n).

Folio Official

March 1, 2026

1 Greatest Common Divisor and Least Common Multiple

Definition 1 (Greatest common divisor).

For integers

a, b

, not both zero, the greatest common divisor of

a

and

b

is the largest positive integer

d

satisfying

d ∣ a

and

d ∣ b

. We write

d = g cd (a, b)

. When

g cd (a, b) = 1

, we say

a

and

b

are coprime.

Definition 2 (Least common multiple).

For positive integers

a, b

, the least common multiple is the smallest positive integer

m

satisfying

a ∣ m

and

b ∣ m

. We write

m = lcm (a, b)

Theorem 3.

For positive integers

a, b

, we have

g cd (a, b) \cdot lcm (a, b) = ab

Proof.

Set

d = g cd (a, b)

and write

a = d a^{'}

b = d b^{'}

with

g cd (a^{'}, b^{'}) = 1

. It suffices to show that

lcm (a, b) = d a^{'} b^{'}

. Clearly

a ∣ d a^{'} b^{'}

and

b ∣ d a^{'} b^{'}

. Now let

m

be any positive integer with

a ∣ m

and

b ∣ m

. Write

m = d a^{'} k

. Then

d b^{'} ∣ d a^{'} k

, so

b^{'} ∣ a^{'} k

. Since

g cd (a^{'}, b^{'}) = 1

, we obtain

b^{'} ∣ k

, and therefore

d a^{'} b^{'} ∣ m

. Hence

lcm (a, b) = d a^{'} b^{'} = ab / d

. □

2 The Euclidean Algorithm

Theorem 4 (Correctness of the Euclidean algorithm).

For positive integers

a \geq b

, write

a = b q + r

with

0 \leq r < b

by the division algorithm. Then

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

Proof.

d ∣ a

and

d ∣ b

, then

d ∣ (a - b q) = d ∣ r

. Conversely, if

d ∣ b

and

d ∣ r

, then

d ∣ (b q + r) = d ∣ a

. Thus the sets of common divisors of

{a, b}

and

{b, r}

coincide, and in particular their maxima agree. □

Remark 5.

Applying this theorem repeatedly yields

g cd (a, b) = g cd (b, r_{1}) = g cd (r_{1}, r_{2}) = \dots

, with the remainders strictly decreasing until we reach

g cd (r_{k - 1}, 0) = r_{k - 1}

. This is the Euclidean algorithm.

Theorem 6 (Complexity).

The Euclidean algorithm terminates in

O (lo g min (a, b))

iterations.

Proof.

In the step

a = b q + r

, we have

r < b

; in fact, one can show

r \leq a /2

. If

b \leq a /2

, then

r < b \leq a /2

. If

b > a /2

, then

q = 1

and

r = a - b < a /2

. Therefore the remainder is at least halved every two iterations, giving

O (lo g min (a, b))

total steps. □

3 Bézout's Identity

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

For integers

a, b

, not both zero, there exist integers

x, y

such that

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

Proof.

Consider the set

S = {a x + b y ∣ x, y \in Z, a x + b y > 0}

. Since

S \neq = \emptyset

(for instance,

a^{2} + b^{2} > 0

belongs to

S

for a suitable combination), the well-ordering principle furnishes a least element

d = a x_{0} + b y_{0}

. We claim

d ∣ a

. By the division algorithm,

a = d q + r

with

0 \leq r < d

. Then

r = a - d q = a (1 - q x_{0}) + b (- q y_{0})

lies in

S \cup {0}

. Since

r < d

and

d

is the least element of

S

, we must have

r = 0

, so

d ∣ a

. Similarly

d ∣ b

, so

d

is a common divisor. Conversely, if

c ∣ a

and

c ∣ b

, then

c ∣ d

, which forces

d = g cd (a, b)

. □

4 The Extended Euclidean Algorithm

The extended Euclidean algorithm computes, alongside $g cd (a, b)$ , the Bé $x, y$ satisfying $a x + b y = g cd (a, b)$ .

Example 8.

Compute

g cd (252, 198)

252 = 1 \cdot 198 + 54

198 = 3 \cdot 54 + 36

54 = 1 \cdot 36 + 18

36 = 2 \cdot 18 + 0

. Hence

g cd (252, 198) = 18

. Back-substituting:

18 = 54 - 1 \cdot 36 = 54 - 1 \cdot (198 - 3 \cdot 54) = 4 \cdot 54 - 198 = 4 (252 - 198) - 198 = 4 \cdot 252 - 5 \cdot 198

5 Solving Linear Congruences

Theorem 9.

The congruence

a x \equiv b (mod n)

has a solution if and only if

g cd (a, n) ∣ b

. When solutions exist, there are exactly

d = g cd (a, n)

solutions modulo

n

Proof.

The congruence

a x \equiv b (mod n)

is equivalent to the existence of integers

x, y

with

a x + n y = b

. By Bé

{a x + n y ∣ x, y \in Z} = g cd (a, n) Z

, so

b

lies in this set precisely when

g cd (a, n) ∣ b

. When

d = g cd (a, n) ∣ b

, the reduced congruence

(a / d) x \equiv b / d (mod n / d)

has

g cd (a / d, n / d) = 1

and therefore a unique solution

x_{0}

. The solutions of the original congruence are

x \equiv x_{0} + kn / d (mod n)

for

k = 0, 1, \dots, d - 1

, giving

d

solutions in all. □

Number Theory Algebra Textbook Euclidean Algorithm GCD

Folio Official

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

1 followers·107 articles

The Greatest Common Divisor and the Euclidean Algorithm — Algebraic Foundations of an Algorithm

Folio Official

March 1, 2026

1 Greatest Common Divisor and Least Common Multiple

Definition 1 (Greatest common divisor).

For integers

a, b

, not both zero, the greatest common divisor of

a

and

b

is the largest positive integer

d

satisfying

d ∣ a

and

d ∣ b

. We write

d = g cd (a, b)

. When

g cd (a, b) = 1

, we say

a

and

b

are coprime.

Definition 2 (Least common multiple).

For positive integers

a, b

, the least common multiple is the smallest positive integer

m

satisfying

a ∣ m

and

b ∣ m

. We write

m = lcm (a, b)

Theorem 3.

For positive integers

a, b

, we have

g cd (a, b) \cdot lcm (a, b) = ab

Proof.

Set

d = g cd (a, b)

and write

a = d a^{'}

b = d b^{'}

with

g cd (a^{'}, b^{'}) = 1

. It suffices to show that

lcm (a, b) = d a^{'} b^{'}

. Clearly

a ∣ d a^{'} b^{'}

and

b ∣ d a^{'} b^{'}

. Now let

m

be any positive integer with

a ∣ m

and

b ∣ m

. Write

m = d a^{'} k

. Then

d b^{'} ∣ d a^{'} k

, so

b^{'} ∣ a^{'} k

. Since

g cd (a^{'}, b^{'}) = 1

, we obtain

b^{'} ∣ k

, and therefore

d a^{'} b^{'} ∣ m

. Hence

lcm (a, b) = d a^{'} b^{'} = ab / d

. □

2 The Euclidean Algorithm

Theorem 4 (Correctness of the Euclidean algorithm).

For positive integers

a \geq b

, write

a = b q + r

with

0 \leq r < b

by the division algorithm. Then

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

Proof.

d ∣ a

and

d ∣ b

, then

d ∣ (a - b q) = d ∣ r

. Conversely, if

d ∣ b

and

d ∣ r

, then

d ∣ (b q + r) = d ∣ a

. Thus the sets of common divisors of

{a, b}

and

{b, r}

coincide, and in particular their maxima agree. □

Remark 5.

Applying this theorem repeatedly yields

g cd (a, b) = g cd (b, r_{1}) = g cd (r_{1}, r_{2}) = \dots

, with the remainders strictly decreasing until we reach

g cd (r_{k - 1}, 0) = r_{k - 1}

. This is the Euclidean algorithm.

Theorem 6 (Complexity).

The Euclidean algorithm terminates in

O (lo g min (a, b))

iterations.

Proof.

In the step

a = b q + r

, we have

r < b

; in fact, one can show

r \leq a /2

. If

b \leq a /2

, then

r < b \leq a /2

. If

b > a /2

, then

q = 1

and

r = a - b < a /2

. Therefore the remainder is at least halved every two iterations, giving

O (lo g min (a, b))

total steps. □

3 Bézout's Identity

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

For integers

a, b

, not both zero, there exist integers

x, y

such that

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

Proof.

Consider the set

S = {a x + b y ∣ x, y \in Z, a x + b y > 0}

. Since

S \neq = \emptyset

(for instance,

a^{2} + b^{2} > 0

belongs to

S

for a suitable combination), the well-ordering principle furnishes a least element

d = a x_{0} + b y_{0}

. We claim

d ∣ a

. By the division algorithm,

a = d q + r

with

0 \leq r < d

. Then

r = a - d q = a (1 - q x_{0}) + b (- q y_{0})

lies in

S \cup {0}

. Since

r < d

and

d

is the least element of

S

, we must have

r = 0

, so

d ∣ a

. Similarly

d ∣ b

, so

d

is a common divisor. Conversely, if

c ∣ a

and

c ∣ b

, then

c ∣ d

, which forces

d = g cd (a, b)

. □

4 The Extended Euclidean Algorithm

The extended Euclidean algorithm computes, alongside $g cd (a, b)$ , the Bé $x, y$ satisfying $a x + b y = g cd (a, b)$ .

Example 8.

Compute

g cd (252, 198)

252 = 1 \cdot 198 + 54

198 = 3 \cdot 54 + 36

54 = 1 \cdot 36 + 18

36 = 2 \cdot 18 + 0

. Hence

g cd (252, 198) = 18

. Back-substituting:

18 = 54 - 1 \cdot 36 = 54 - 1 \cdot (198 - 3 \cdot 54) = 4 \cdot 54 - 198 = 4 (252 - 198) - 198 = 4 \cdot 252 - 5 \cdot 198

5 Solving Linear Congruences

Theorem 9.

The congruence

a x \equiv b (mod n)

has a solution if and only if

g cd (a, n) ∣ b

. When solutions exist, there are exactly

d = g cd (a, n)

solutions modulo

n

Proof.

The congruence

a x \equiv b (mod n)

is equivalent to the existence of integers

x, y

with

a x + n y = b

. By Bé

{a x + n y ∣ x, y \in Z} = g cd (a, n) Z

, so

b

lies in this set precisely when

g cd (a, n) ∣ b

. When

d = g cd (a, n) ∣ b

, the reduced congruence

(a / d) x \equiv b / d (mod n / d)

has

g cd (a / d, n / d) = 1

and therefore a unique solution

x_{0}

. The solutions of the original congruence are

x \equiv x_{0} + kn / d (mod n)

for

k = 0, 1, \dots, d - 1

, giving

d

solutions in all. □

Number Theory Algebra Textbook Euclidean Algorithm GCD

Folio Official

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

1 followers·107 articles

The Greatest Common Divisor and the Euclidean Algorithm — Algebraic Foundations of an Algorithm

1 Greatest Common Divisor and Least Common Multiple

2 The Euclidean Algorithm

3 Bézout's Identity

4 The Extended Euclidean Algorithm

5 Solving Linear Congruences

Share your expertise with the world

More from Folio Official

Introduction to Algebraic Integers — Extending the Notion of Integer

Arithmetic Functions and Multiplicative Functions — Functions on the Integers

Primes and the Fundamental Theorem of Arithmetic — The Atomic Decomposition of Integers

Chebyshev's Estimates: 0.92 x/ln x < π(x) < 1.11 x/ln x and the Prime Number Theorem

The Greatest Common Divisor and the Euclidean Algorithm — Algebraic Foundations of an Algorithm

1 Greatest Common Divisor and Least Common Multiple

2 The Euclidean Algorithm

3 Bézout's Identity

4 The Extended Euclidean Algorithm

5 Solving Linear Congruences

Share your expertise with the world

More from Folio Official

Introduction to Algebraic Integers — Extending the Notion of Integer

Arithmetic Functions and Multiplicative Functions — Functions on the Integers

Primes and the Fundamental Theorem of Arithmetic — The Atomic Decomposition of Integers

Chebyshev's Estimates: 0.92 x/ln x < π(x) < 1.11 x/ln x and the Prime Number Theorem