Understanding the Euclidean Algorithm: A Simple Guide for Beginners

Have you ever typed =100/45 into Excel or Google Sheets, formatted it as a fraction, and watched it magically turn into 20/9?

Seems simple. But under the hood, it’s using one of the oldest and smartest math tricks ever invented — the Euclidean Algorithm.
Let’s break down how that works — without jargon, just logic.

---

🤔 Why Would I Need This?

GCD is surprisingly useful:

• 🧾 Simplifying ratios like 30:12 → 5:2

• ⏰ Aligning events or schedules (like "every 12 days" and "every 18 days")

• 🔐 Encryption and tech stuff (RSA, key generation)

• 📊 Reducing fractions in Excel and calculators

---

💡 What Even Is GCD?

GCD stands for Greatest Common Divisor. It’s the largest number that divides two numbers exactly (no remainders).

Example:
GCD(30, 12) = 6, because 6 is the biggest number that divides both.

👉 We use the GCD to simplify fractions — by dividing both the numerator and denominator by it, just like Excel does when it turns 100/45 into 20/9.

---

🪓 Brute Force: Why It’s Not the Best

You could try listing out all the divisors of both numbers and pick the largest one they have in common.

Example: GCD(30, 12)

• Divisors of 30: 1, 2, 3, 5, 6, 10, 15, 30

• Divisors of 12: 1, 2, 3, 4, 6, 12
  → Common divisors: 1, 2, 3, 6 → So GCD = 6

That works… but imagine doing this for huge numbers like 10,000 and 6,433.
Listing all factors becomes slow, inefficient, and error-prone.

---

🌀 Enter: The Euclidean Algorithm

This algorithm is over 2,000 years old and still the fastest way to find the GCD — especially when numbers get big.

The basic steps:

1. Take two numbers: a and b, where a > b

2. Replace a with b, and b with a % b (the remainder)

3. Keep repeating until the remainder is 0

4. The divisor in the step where remainder becomes 0 is the GCD

---

🔄 But Why Do We Keep Replacing Like That?

Ah, here’s the real question — the heart of it all:

Why are we replacing the bigger number with the smaller one and then taking the remainder?

Answer: Because it simplifies the problem without changing the answer — making it easier and dramatically faster to solve.

Let’s take an example:

Start with GCD(30, 12)

• 30 ÷ 12 = 2 remainder 6 → So we write 30 = 12 × 2 + 6

• Now solve GCD(12, 6) instead — same logic, smaller numbers.

Why does this help?

• ✅ Smaller numbers are easier to work with

• ✅ Each step removes a chunk that doesn’t change the GCD

• ✅ Each remainder step reduces the size of numbers significantly, so we get to the final answer faster

⏱️ In fact, the remainder is often less than half of the smaller number — so the problem size drops quickly.

That’s why the Euclidean Algorithm finishes in just a few steps — its time complexity is only O(log min(a, b)).

It’s like peeling an onion — each layer removed brings us closer to the core: the GCD — fast.

---

🧹 Why Do We Replace with the Remainder?

🍕 Visualize It: The Pizza Slice Trick

Imagine you have two pizza crusts:

• One is 30 cm, the other 12 cm.
  You want to slice both into equal parts with no leftovers.

You try slicing both with 12 cm pieces:

• From 30 cm, you get 2 slices (12 × 2 = 24), and 6 cm is left.

So now the real question becomes:

What’s the largest slice that fits exactly into 12 and 6?

That’s GCD(12, 6) — and that turns out to be 6.

This leftover (the remainder) shows where the unevenness begins — and helps us zoom in on the shared factor.
Each remainder reveals only what’s truly shared — and throws away the rest.

---

🤯 But How Does That Even Work Mathematically?

Let’s suppose you want to prove that GCD(30, 12) = GCD(12, 6).

From the equation:
30 = 12 × 2 + 6
We rearrange:
6 = 30 - 12 × 2

Now let’s say some number d divides both 12 and 6:

• Then it divides 12 × 2

• And it divides 6

• So it must divide 30 = 12×2 + 6

✅ That means: Any number that divides 12 and 6 also divides 30.

So solving GCD(12, 6) is just as good as solving GCD(30, 12) — but it’s faster because the numbers are smaller.

---

🔢 Full Example: GCD(48, 18)

48 ÷ 18 = 2 remainder 12   →  replace (48, 18) → (18, 12)  
18 ÷ 12 = 1 remainder 6    →  replace (18, 12) → (12, 6)  
12 ÷ 6  = 2 remainder 0    →  ✅ STOP!

---

🎯 Final Answer: GCD = 6
Because 6 is the number that divided the previous number (12) exactly, making the remainder 0.
✅ That final divisor — the one that causes the remainder to be 0 — is the GCD.

---

🔁 So What’s the Big Idea?

The Euclidean Algorithm is basically saying:

“Let’s keep replacing the bigger number with the smaller one, and the smaller one with the remainder — until we find the number that divides the last one exactly.”

That number — the last divisor — is the GCD.
It’s pure. It’s efficient. And it always works.

---

🐍 Python Code: Recursive GCD

Here's how you can implement the Euclidean Algorithm recursively in Python:

# Recursive function to compute GCD using Euclidean Algorithm
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# Example usage
print(gcd(30, 12))  # Output: 6
print(gcd(48, 18))  # Output: 6

This function keeps calling itself with (b, a % b) until b becomes 0 — and then returns the last non-zero value, which is the GCD.

---

✨ Final Words

So next time you hear “find the GCD,” don’t just plug numbers into a formula.

Remember:

• You replace the bigger number with the smaller one to shrink the problem

• You take the remainder because it strips away what’s not shared

• You stop when remainder becomes 0 — and the number that caused that?
  ✨ That’s your GCD

You’re not just doing math — you’re revealing the strongest connection between two numbers.
That’s the Euclidean Algorithm. Ancient, fast, and still awesome.