Chapter 3: The Euclidean Algorithm

An efficient algorithm for computing the greatest common divisor

Introduction

The Euclidean algorithm is an efficient method for computing the greatest common divisor (GCD) of two positive integers. It appears in Euclid's Elements (circa 300 BC) and is regarded as one of the oldest known algorithms.

Why do we need the Euclidean algorithm?

Computing the GCD via prime factorization becomes inefficient for large numbers because trial division grows costly. Using the Euclidean algorithm, even $\gcd(12345678, 87654321)$ can be computed in only 13 divisions.

Principle of the Algorithm

Theorem (Division-based GCD reduction)

For positive integers $a, b$ with $a > b$, let $q$ be the quotient and $r$ the remainder when $a$ is divided by $b$:

$$a = bq + r \quad (0 \leq r < b)$$

Then

$$\gcd(a, b) = \gcd(b, r)$$

Proof

Let $d = \gcd(a, b)$. Then $d \mid a$ and $d \mid b$.

Step 1: Show that $d \mid r$

Since $r = a - bq$, and $d \mid a$ and $d \mid bq$, it follows that $d \mid r$.

Step 2: Show that $\gcd(b, r) = d$

$d$ is a common divisor of $b$ and $r$.

Let $d' = \gcd(b, r)$. Then $d' \mid b$ and $d' \mid r$, so

$d' \mid (bq + r) = a$

Hence $d'$ is a common divisor of $a$ and $b$, so $d' \leq d$.

On the other hand, $d \leq d'$ (since $d$ is a common divisor of $b$ and $r$), so $d = d'$.

Therefore $\gcd(a, b) = \gcd(b, r)$. $\square$

a b b b r q copies of b Divisors of a and b ⇔ Divisors of b and r (The remainder r is smaller, so the problem becomes simpler!)
Figure 1: Principle of the Euclidean algorithm — $\gcd(a, b) = \gcd(b, r)$

The Algorithm

The Euclidean Algorithm

Input: positive integers $a, b$ with $a \geq b$

Output: $\gcd(a, b)$

  1. $r \leftarrow a \mod b$ (the remainder when $a$ is divided by $b$)
  2. If $r = 0$, output $b$ and terminate
  3. Set $a \leftarrow b$, $b \leftarrow r$ and go to step 1

Example: Find $\gcd(252, 105)$

\begin{align} 252 &= 105 \times 2 + 42 & \gcd(252, 105) &= \gcd(105, 42) \\ 105 &= 42 \times 2 + 21 & \gcd(105, 42) &= \gcd(42, 21) \\ 42 &= 21 \times 2 + 0 & \gcd(42, 21) &= 21 \end{align}

Answer: $\gcd(252, 105) = 21$

252 ÷ 105 = 2 rem 42 105 ÷ 42 = 2 rem 21 42 ÷ 21 = 2 rem 0 Done!
$\gcd(252, 105) = 21$
Figure 2: Computing gcd(252, 105) step by step

Extended Euclidean Algorithm

Theorem (Bézout's identity)

For integers $a, b$ with $d = \gcd(a, b)$, there exist integers $x, y$ such that

$$ax + by = d$$

Proof (constructive)

By tracing the steps of the Euclidean algorithm in reverse, we can find $x$ and $y$.

Example: For $\gcd(252, 105) = 21$, find $x, y$ satisfying $252x + 105y = 21$

Express each step of the Euclidean algorithm:

\begin{align} 252 &= 105 \times 2 + 42 & \Rightarrow \quad 42 &= 252 - 105 \times 2 \\ 105 &= 42 \times 2 + 21 & \Rightarrow \quad 21 &= 105 - 42 \times 2 \end{align}

Back-substitution:

\begin{align} 21 &= 105 - 42 \times 2 \\ &= 105 - (252 - 105 \times 2) \times 2 \\ &= 105 - 252 \times 2 + 105 \times 4 \\ &= 252 \times (-2) + 105 \times 5 \end{align}

Therefore $x = -2, y = 5$. $\square$

substitute x = −2 y = 5
$42 = 252 - 105 \times 2$
$21 = 105 - 42 \times 2$
$21 = 105 - (252 - 105 \times 2) \times 2$
$21 = 252 \times (-2) + 105 \times 5$
Figure 3: Extended Euclidean Algorithm (back-substitution)

Application to Linear Diophantine Equations

Theorem: Solutions of linear Diophantine equations

For integers $a, b, c$, the equation $ax + by = c$ has integer solutions if and only if

$$\gcd(a, b) \mid c$$

(i.e., $\gcd(a, b)$ divides $c$)

Proof

Necessity: Let $d = \gcd(a, b)$. Since $d \mid a$ and $d \mid b$, we have $d \mid (ax + by) = c$.

Sufficiency: If $d \mid c$, write $c = dk$.

By Bézout's identity, there exist $x_0, y_0$ with $ax_0 + by_0 = d$.

Multiplying both sides by $k$: $a(kx_0) + b(ky_0) = dk = c$.

So $x = kx_0, y = ky_0$ is a solution. $\square$

General solution

If $(x_0, y_0)$ is a particular solution of $ax + by = c$ and $d = \gcd(a, b)$, then the general solution is

$$x = x_0 + \frac{b}{d}t, \quad y = y_0 - \frac{a}{d}t \quad (t \in \mathbb{Z})$$

Worked example

Find all integer solutions of $252x + 105y = 63$.

Solution

$\gcd(252, 105) = 21$ and $21 \mid 63$ (since $63 = 21 \times 3$), so solutions exist.

Multiplying $252 \times (-2) + 105 \times 5 = 21$ by 3 gives

$252 \times (-6) + 105 \times 15 = 63$

Particular solution: $(x_0, y_0) = (-6, 15)$

General solution: $x = -6 + 5t, \quad y = 15 - 12t \quad (t \in \mathbb{Z})$

Efficiency of the Algorithm

Theorem (Lamé's theorem)

When computing $\gcd(a, b)$ with the Euclidean algorithm (where $a > b$), the number of divisions is at most five times the number of decimal digits of $b$.

Computational complexity

The time complexity of the Euclidean algorithm is $O(\log(\min(a, b)))$. This is highly efficient and serves as the foundation for practical algorithms such as RSA encryption.

The worst case occurs for consecutive Fibonacci numbers $\gcd(F_{n+1}, F_n)$, where the quotient is always $1$ at each step, making the remainder decrease as slowly as possible. The proof is given in Basic: Euclidean Algorithm.

Example with large numbers

Find $\gcd(12345678, 87654321)$:

\begin{align} 87654321 &= 12345678 \times 7 + 1034475 \\ 12345678 &= 1034475 \times 11 + 966453 \\ 1034475 &= 966453 \times 1 + 68022 \\ 966453 &= 68022 \times 14 + 14145 \\ 68022 &= 14145 \times 4 + 11442 \\ 14145 &= 11442 \times 1 + 2703 \\ 11442 &= 2703 \times 4 + 630 \\ 2703 &= 630 \times 4 + 183 \\ 630 &= 183 \times 3 + 81 \\ 183 &= 81 \times 2 + 21 \\ 81 &= 21 \times 3 + 18 \\ 21 &= 18 \times 1 + 3 \\ 18 &= 3 \times 6 + 0 \end{align}

Answer: $\gcd(12345678, 87654321) = 3$

(Completed in only 13 divisions — vastly faster than computing via prime factorization.)