Chapter 54: The Euclidean Algorithm

The Euclidean Algorithm is one of the most beautiful, elegant, and historically important algorithms in all of mathematics and computer science.

It is used to find the Greatest Common Divisor (GCD) of two integers — that is, the largest positive integer that divides both numbers without leaving a remainder.

The algorithm is named after the Greek mathematician Euclid (around 300 BC), and it appears in his book Elements — making it one of the oldest algorithms still in active use today.

Let me explain it to you step by step, very clearly, like we are sitting together and I’m teaching you from scratch.

Core Idea – Very Simple Intuition

Imagine you have two lengths of rope:

• One rope is 48 meters long
• The other is 18 meters long

You want to cut both ropes into pieces of exactly the same length, and you want that length to be as large as possible.

What is the longest possible piece length that can divide both ropes perfectly?

The answer is 6 meters — because:

48 ÷ 6 = 8 pieces 18 ÷ 6 = 3 pieces And no larger number works.

The Euclidean algorithm finds this number (GCD) in a very clever way — without trying every possible divisor.

The Two Main Versions You Should Know

There are two common ways to explain it:

1. Subtraction version (more intuitive, slower)
2. Division (modulo) version (the real, efficient one)

Let’s see both.

Version 1: Subtraction Method (easy to understand)

Rule:

While the two numbers are not equal:

• Subtract the smaller number from the larger number
• Replace the larger number with the result
• Keep going until both numbers become equal
• That equal number is the GCD

Example: GCD(48, 18)

48 > 18 → 48 − 18 = 30 → now (30, 18) 30 > 18 → 30 − 18 = 12 → now (12, 18) 18 > 12 → 18 − 12 = 6 → now (12, 6) 12 > 6 → 12 − 6 = 6 → now (6, 6) Both equal → GCD = 6

Works, but very slow if one number is much larger (e.g. GCD(1000000, 3) would take many subtractions).

Version 2: Division (Modulo) Method – The Real Euclidean Algorithm

This is the version everyone uses in practice.

Rule:

To find GCD(a, b) where a ≥ b:

• Divide a by b → get quotient and remainder
• GCD(a, b) = GCD(b, remainder)
• Repeat until remainder = 0
• The last non-zero remainder is the GCD

In code terms:

Very important property (this is the magic):

GCD(a, b) = GCD(b, a % b) This is mathematically proven and is why the algorithm works.

Step-by-step Example: GCD(1071, 462)

Let’s do it manually:

1071 ÷ 462 = 2 (quotient), remainder = 1071 − 2×462 = 147 → GCD(1071, 462) = GCD(462, 147)

462 ÷ 147 = 3 (quotient), remainder = 462 − 3×147 = 21 → GCD(462, 147) = GCD(147, 21)

147 ÷ 21 = 7 (quotient), remainder = 147 − 7×21 = 0 → GCD(147, 21) = GCD(21, 0) = 21

Answer: GCD(1071, 462) = 21

Check: 1071 ÷ 21 = 51 (exact) 462 ÷ 21 = 22 (exact)

Recursive Version (very clean & common in interviews)

Same logic — just written recursively.

Time Complexity – Very Important

Best case: When b is very small (especially b = 1 or 0) → O(1) or very few steps

Worst case: When numbers are consecutive Fibonacci numbers → Takes O(log n) steps (very fast!)

Average case: Also O(log n)

Why logarithmic?

Each step reduces the size dramatically (a % b < b), and in the worst case it behaves like the Fibonacci sequence — which grows exponentially, so the number of steps is logarithmic.

Real numbers:

• GCD(1,000,000 and 1) → 1 step → O(1)
• GCD(1,000,000 and 999,999) → very few steps
• Worst known case (Fibonacci numbers) → about O(log n) steps even for huge n

Comparison with naive method (trying all divisors):

Naive: O(min(a,b)) → very slow Euclidean: O(log max(a,b)) → extremely fast

Summary – What you should remember & say in interviews

The Euclidean Algorithm finds the Greatest Common Divisor (GCD) of two numbers using repeated division and remainders. The key property is: GCD(a, b) = GCD(b, a % b) Time complexity is O(log min(a,b)) in the worst case — extremely fast even for very large numbers. It is one of the oldest, most elegant, and most useful algorithms in computer science. Main applications:

• Computing GCD
• Reducing fractions
• Modular arithmetic
• Finding LCM (LCM(a,b) = a×b / GCD(a,b))
• Many number theory problems

Bonus – Extended Euclidean Algorithm (very common follow-up)

Not only finds GCD, but also finds integers x and y such that:

ax + by = GCD(a,b)

This is used in:

• Modular inverse
• Linear Diophantine equations
• RSA cryptography

Do you want me to explain the Extended Euclidean Algorithm next (with example), or would you like to see more examples of Euclidean algorithm, or perhaps how it’s used in competitive programming?

Just tell me — I’ll continue in the same detailed, friendly, teacher style 😊