Course contentsShow
← Mathematics
Lesson 2713 of 3,12154. Number TheoryFree lesson

The Euclidean Algorithm

Learn the efficient Euclidean Algorithm for computing the GCD using repeated division with remainder.

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):

  1. Divide a by b to get quotient q and remainder r (from the Division Algorithm: a = bq + r)
  2. Replace a with b and b with r
  3. Repeat until r = 0
  4. 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.