[Introduction to Number Theory Series Part 5] Why Does the Euclidean Algorithm Find the GCD So Fast?

The Euclidean algorithm is the classical fast way to compute the gcd. Its power comes from one idea: replacing a larger pair with a smaller pair without changing the gcd.

What this post covers

• The main identity behind the Euclidean algorithm
• Step-by-step gcd calculations
• Why the process is fast
• How this prepares the way for Bézout's identity

Key terms

• Euclidean algorithm: the repeated-remainder algorithm for finding the gcd
• greatest common divisor: the largest positive common divisor of two integers
• remainder: the value left after integer division
• division algorithm: the standard form a=bq+r

The main identity

For simplicity, suppose first that a \ge b > 0. This is a convenient starting case, not the only case the algorithm can handle. Divide a by b:

$$a=bq+r.$$

Then the key fact is

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

Why? Because any common divisor of a and b also divides r=a-bq, and any common divisor of b and r also divides a=bq+r. So the two pairs have the same common divisors.

Example 1: gcd(48,18)

$$48=18\times 2+12$$ $$18=12\times 1+6$$ $$12=6\times 2+0$$

The last nonzero remainder is 6, so

$$\gcd(48,18)=6.$$

Example 2: gcd(252,105)

$$252=105\times 2+42$$ $$105=42\times 2+21$$ $$42=21\times 2+0$$

So

$$\gcd(252,105)=21.$$

Why is it fast?

A naive method might list all divisors of both numbers and compare them. The Euclidean algorithm instead keeps shrinking the input:

(48,18) -> (18,12) -> (12,6) -> (6,0)

At each step, the numbers become smaller while the gcd stays the same. That is why it feels algorithmic rather than brute-force.

Why does the last nonzero remainder matter?

Each step preserves the gcd. When the process reaches a remainder of 0, the current divisor divides the previous number exactly. So the last nonzero remainder is the gcd of the original pair.

Common mistakes

1. Memorizing the steps without the reason

The algorithm works because \gcd(a,b)=\gcd(b,r), not by magic.

2. Forgetting the role of the division algorithm

Each step depends on writing one integer as a quotient-remainder form.

3. Thinking the order is the main issue

The essential point is not whether you start with the larger number written first. The essential point is repeated reduction by remainder.

Wrap-up

The Euclidean algorithm finds the gcd quickly because it keeps replacing a pair by a smaller pair with the same gcd. The last nonzero remainder is the answer.

Next we go one step deeper: the gcd is not only a divisor. Through Bézout's identity, it can also be written as ax+by.