The Euclidean Algorithm – The Fastest Way to Find the GCF

The Euclidean Algorithm is a method for finding the GCF of two numbers that was described by the Greek mathematician Euclid around 300 BC. It remains one of the most efficient algorithms in all of mathematics, even for very large numbers.

Historians of mathematics often call this the oldest nontrivial algorithm still in everyday use — the Greeks themselves called the underlying idea anthyphairesis (“reciprocal subtraction”), and it appears in Book VII of Euclid’s Elements essentially unchanged from the version taught today. Donald Knuth, one of the founders of modern computer science, went so far as to call it “the granddaddy of all algorithms” in his classic textbook The Art of Computer Programming, because it is also one of the earliest known examples of a precisely specified, guaranteed-to-terminate step-by-step procedure — the very definition of what an algorithm is.

The Core Idea

GCF(a, b) = GCF(b, a mod b), where “mod” means the remainder when a is divided by b. Repeat until the remainder is 0. The GCF is the last non-zero remainder.

Step-by-Step Example 1

GCF(48, 18)

Step	Division	Remainder
1	48 ÷ 18 = 2 remainder 12	12
2	18 ÷ 12 = 1 remainder 6	6
3	12 ÷ 6 = 2 remainder 0	0 — stop

GCF(48,18) = 6

Step-by-Step Example 2

GCF(252, 105)

Step	Division	Remainder
1	252 ÷ 105 = 2 r 42	42
2	105 ÷ 42 = 2 r 21	21
3	42 ÷ 21 = 2 r 0	0 — stop

GCF(252,105) = 21

Why It Works

If d divides both a and b, it also divides their difference a − b, and any remainder when a is divided by b. So the set of common divisors of (a, b) is identical to that of (b, remainder). We keep reducing until one number is 0, leaving the GCF.

Key Takeaways

Divide the larger by the smaller; take the remainder.
Replace the larger with the smaller and the smaller with the remainder.
Repeat until the remainder is 0; the GCF is the last non-zero remainder.
Far faster than listing factors for large numbers.
Once GCF is found, use LCM = (a × b) ÷ GCF.

Practice: Euclidean Algorithm

Find the GCF Step by Step