The Euclidean Algorithm
You'll learn a lightning-fast method to compute the greatest common divisor of two numbers using repeated division.
The Core Idea
In the previous lesson, you saw how to find the GCD by listing all divisors of both numbers and picking the largest common one. That works, but it's tedious for large numbers. The Euclidean Algorithm gives you a much faster way: it uses the fact that gcd(a, b) = gcd(b, r) where r is the remainder when you divide a by b.
Think of it like peeling away layers: instead of checking every divisor, you repeatedly replace the larger number with the remainder until one number becomes zero. The last non-zero remainder is your GCD.
How It Works
Start with two positive integers a and b (assume a ≥ b):
- Divide
abybto get quotientqand remainderr(from the Division Algorithm:a = bq + r) - Replace
awithbandbwithr - Repeat until
r = 0 - The GCD is the last non-zero remainder
Example: Find gcd(48, 18)
48 = 18·2 + 12→ next pair: (18, 12)18 = 12·1 + 6→ next pair: (12, 6)12 = 6·2 + 0→ stop!
The last non-zero remainder is 6, so gcd(48, 18) = 6.
Why It Works
Each step preserves the set of common divisors. Any number dividing both a and b must also divide r = a - bq. Conversely, any number dividing b and r must divide a = bq + r. Since remainders decrease at each step, you eventually reach zero, and the process terminates.
Key Takeaway: The Euclidean Algorithm computes the GCD efficiently through repeated division, replacing (a, b) with (b, remainder) until the remainder is zero.