GCD

Dec 7, 2025

Updated 1 day ago

6 min read

GCD & The Euclidean Algorithm — Why a 2300-Year-Old Trick Still Beats Everything

Every article tells you the formula. Almost none explain why it works — or why a Greek mathematician's insight from 300 BC is still the fastest approach we have.

I used to think GCD was a solved, boring topic. You learn it in school, you move on. Then I sat down with a competitive programming problem that needed GCD on 10⁶ queries and reached for the naive approach — checking every divisor up to min(a, b).

It timed out. Of course it did.

That's when I actually read how the Euclidean Algorithm works, not just what it outputs. And I realized: this thing is elegant in a way that most DSA topics aren't. It doesn't just compute an answer — it proves something about numbers at every step.

What Even Is GCD?

The Greatest Common Divisor of two integers a and b is the largest integer d such that d divides both a and b without a remainder.

g cd (a, b) = d where d ∣ a and d ∣ b and d is maximum

Simple examples:

a	b	GCD
12	8	4
100	75	25
17	13	1
48	18	6

When $g cd (a, b) = 1$ , the numbers are called coprime — they share no common factor other than 1. This turns out to matter a lot in cryptography, modular arithmetic, and fraction simplification.

The Naive Approach (and Why It Fails)

The obvious method: loop from 1 to min(a, b) and track the largest divisor of both.

cpp

int gcd_naive(int a, int b) {
    int result = 1;
    for (int i = 1; i <= min(a, b); i++) {
        if (a % i == 0 && b % i == 0)
            result = i;
    }
    return result;
}

Time Complexity: $O (min (a, b))$

For small inputs, this is fine. For a = 10^9, b = 10^9 - 1? You're running a billion iterations. On a competitive programming judge with a 1-second limit, this is dead on arrival.

There has to be a better way. And there is — and it's been known since ~300 BC.

The Key Insight: Why Does the Remainder Work?

Here's the mathematical fact that the Euclidean Algorithm is built on:

g cd (a, b) = g cd (b, a mod b)

Let's make sure this isn't just a formula we accept blindly — let's understand why it's true.

Claim: Any divisor of both a and b is also a divisor of a mod b.

Proof sketch: If $d ∣ a$ and $d ∣ b$ , then $d ∣ (a - k b)$ for any integer $k$ . But $a mod b = a - ⌊ a / b ⌋ \cdot b$ , which is exactly of the form $a - k b$ . So $d ∣ (a mod b)$ .

This means the set of common divisors of (a, b) is identical to the set of common divisors of (b, a mod b). Same set → same maximum → same GCD.

That's not a trick. That's a proof. Every step of the Euclidean Algorithm isn't just "making the numbers smaller" — it's preserving the exact same GCD while shrinking the problem.

The Algorithm

plaintext

GCD(a, b):
    if b == 0:
        return a
    return GCD(b, a mod b)

Or iteratively (often preferred to avoid stack overhead):

cpp

int gcd(int a, int b) {
    while (b != 0) {
        a = a % b;
        swap(a, b);
    }
    return a;
}

The loop terminates because a mod b < b always — the second argument strictly decreases every iteration until it hits 0.

Full Trace: gcd(48, 18)

Step	a	b	a mod b
1	48	18	12
2	18	12	6
3	12	6	0
4	6	0	—

Result: 6 ✓

Each row you can verify: 48 = 2 × 18 + 12, 18 = 1 × 12 + 6, 12 = 2 × 6 + 0. The GCD never changes — we're just peeling away the problem.

Time Complexity — The Fibonacci Worst Case

Here's a fact that isn't obvious: the worst-case input for the Euclidean Algorithm is consecutive Fibonacci numbers.

Try gcd(F(n), F(n-1)) — it will take exactly n steps, each reducing by just one Fibonacci term. This gives us the formal bound:

T (n) = O (lo g min (a, b))

Why log? Because it can be proven that in any two consecutive steps, a reduces by at least half. So the number of steps is bounded by $2 lo g_{2} (min (a, b))$ .

For a = b = 10^9, that's roughly 60 steps instead of a billion. This is the difference between "your solution passes" and "your solution gets TLE in round 1."

	Naive	Euclidean
Time	$O (min (a, b))$	$O (lo g min (a, b))$
Space	$O (1)$	$O (1)$ iter / $O (lo g n)$ recursive

LCM From GCD — One Line

The Least Common Multiple (LCM) has a direct relationship with GCD:

lcm (a, b) = \frac{a \times b}{g cd ( a , b )}

cpp

long long lcm(long long a, long long b) {
    return (a / gcd(a, b)) * b;  // Divide first to avoid overflow
}

Note the divide-first trick: (a / gcd(a, b)) * b instead of (a * b) / gcd(a, b). If a and b are both near $1 0^{9}$ , their product overflows a 64-bit integer. Dividing first keeps you safe.

Extended Euclidean Algorithm (Bonus: When It Gets Interesting)

The standard Euclidean Algorithm finds gcd(a, b). The Extended version also finds integers x and y such that:

a x + b y = g cd (a, b)

This is called Bézout's identity, and it's the backbone of:

Modular multiplicative inverse
RSA encryption key generation
Solving linear Diophantine equations

cpp

int extGCD(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    int x1, y1;
    int d = extGCD(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return d;
}

We won't derive it fully here, but knowing it exists matters — because every time you see "find modular inverse" in a problem, Extended Euclidean is either the answer or one step away from it.

Where You'll Actually Use This

GCD isn't just a textbook concept. Here's where it shows up in real problems:

Competitive Programming:

Array problems where you need GCD of a range (Sparse Table + GCD)
"Can these values be made equal?" — usually reduces to GCD
Fraction normalization and ratio problems

Real Systems:

Frame rate synchronization (display and game loop GCD)
Gear ratios in mechanical engineering simulations
Hash table sizing (ensuring coprime moduli)
Cryptography — RSA's correctness proof rests on GCD = 1

Classic DSA Patterns:

Segment Tree with GCD queries — $O (lo g n)$ range GCD
Fenwick Tree isn't typically used for GCD (not invertible), but understanding why teaches you about what operations trees can support

Quick Self-Test

Before closing this tab:

Q1: What is $g cd (100, 0)$ ? (Hint: base case)
Q2: Why do we divide before multiplying in the LCM formula?
Q3: What's the worst-case input for Euclidean Algorithm and why?
Q4: If $g cd (a, b) = 1$ , what does that tell you about $lcm (a, b)$ ?

(Answers: 100. To prevent overflow when a·b exceeds int/long range. Consecutive Fibonacci numbers, because they reduce slowest — each step only removes one Fibonacci unit. lcm(a,b) = a·b, since they share no common factor.)

From the DAA and DSA series on NoteHub — these connect directly to what we just covered:

Algorithm Basics — what makes a solution an algorithm, correctness and termination
Asymptotic Notation — reading O(log n) properly and comparing it to O(n)
Comparison of Two Functions — log n vs n vs n² growth rate intuition
Binary Search (Recurrence Relation) — another O(log n) algorithm built on halving the problem
Tower of Hanoi — the other classic recursion problem; complement to this one
Dynamic Programming & 0/1 Knapsack — memoization applied to overlapping subproblems
Greedy Approach for Algorithm Design — Euclidean is implicitly greedy: always take the largest possible reduction
Segment Tree — can be adapted for range GCD queries
Fenwick Tree — related range query structure; understand why GCD doesn't fit here
Full DAA Notes Index

External References

Euclidean Algorithm — Wikipedia — full proof of termination, Fibonacci worst case, and historical context
Visualgo: GCD Visualization — step-by-step animated trace of the algorithm
CP-Algorithms: GCD & LCM — extended Euclidean, Binary GCD, and competitive programming patterns
CP-Algorithms: Extended Euclidean — Bézout's identity, modular inverse derivation
CLRS Chapter 31 — number-theoretic algorithms including formal correctness proof

Part of the DAA Design and Analysis series on NoteHub.

GCD