Euclidean Algorithm
What is it for?
The Euclidean Algorithm is a systematic method for determining the greatest common divisor (GCD) of two integers.
How the Euclidean Algorithm Works
Given two integers a and b satisfying the condition:
$$ a \geq b \geq 0 $$
The algorithm repeatedly applies the division algorithm, expressing a as:
$$ a = qb + r $$
where q is the quotient and r is the remainder, with:
$$ 0 \leq r < b $$
If r is nonzero, we repeat the process by replacing a with b and b with r:
$$ b = q_2r + r_2 $$
The algorithm continues until the remainder becomes zero. The last nonzero remainder encountered is the greatest common divisor of a and b.
A Step-by-Step Example
Let’s compute the GCD of a = 48 and b = 32.
Since:
$$ 48 \geq 32 \geq 0 $$
we proceed with the division:
$$ 48 \div 32 = 1 \quad \text{remainder } 16 $$
As the remainder is nonzero, we continue:
$$ 32 \div 16 = 2 \quad \text{remainder } 0 $$
At this point, the remainder is zero. The last nonzero remainder, 16, is the greatest common divisor:
$$ GCD(48, 32) = 16 $$
We have thus computed the GCD of the two integers using the Euclidean Algorithm.
How Many Steps Does It Take?
The Euclidean Algorithm requires at most b steps to compute GCD(a, b), where b is the smaller of the two integers.
This provides a theoretical upper bound on the number of iterations, though it is rarely tight in practice.
Example
In the example above, computing GCD(48, 32) would, in theory, require no more than 32 steps.
Clearly, this is an overestimate - only two steps were actually needed.
According to Lamé’s Theorem, the number of steps in the Euclidean Algorithm to compute GCD(a, b) is at most proportional to the number of digits in b. In particular, the number of steps is bounded above by: $$ \text{Maximum number of steps} \leq 5k $$ where k is the number of decimal digits in b.
Example
Again, let b = 32. Since 32 has two digits (i.e., k = 2):
$$ \text{Maximum number of steps} \leq 5 \cdot 2 = 10 $$
This bound, though still conservative, is much closer to the actual behavior of the algorithm in typical cases.
And so on.
