Euclidean Algorithm- Finding GCD Made Easy

What Is the Euclidean Algorithm?

The Euclidean algorithm is a method for finding the greatest common divisor (GCD) of two numbers. It's been around for over 2,000 years. Euclid described it in his Elements book around 300 BCE.

Here's the blunt truth: if you need to find the GCD of large numbers, this algorithm is the fastest way. No brute force division by every number up to the minimum. No wasted computation.

Why You Need It

You need the GCD constantly in programming, cryptography, and number theory problems. Finding it manually by listing divisors works for tiny numbers. For anything real, you need this.

How It Works

The algorithm is stupidly simple:

Step 1: Divide the larger number by the smaller number. Keep the remainder.

Step 2: Replace the larger number with the smaller number, and the smaller number with the remainder.

Step 3: Repeat until the remainder is 0. The last non-zero remainder is your GCD.

That's it. The math behind it: GCD(a, b) = GCD(b, a mod b).

The Division Step in Action

When you divide a by b, you get a quotient and a remainder. You only care about the remainder. The Euclidean algorithm strips away everything except what matters.

Real Examples

Example 1: GCD of 48 and 18

Step 1: 48 ÷ 18 = 2 remainder 12

Step 2: Now find GCD(18, 12). 18 ÷ 12 = 1 remainder 6

Step 3: Now find GCD(12, 6). 12 ÷ 6 = 2 remainder 0

Stop. The last non-zero remainder is 6. That's your GCD.

Example 2: GCD of 1071 and 462

Let's walk through this one:

• 1071 ÷ 462 = 2 remainder 147
• 462 ÷ 147 = 3 remainder 21
• 147 ÷ 21 = 7 remainder 0

GCD = 21

You can verify: 1071 ÷ 21 = 51, 462 ÷ 21 = 22. Both are integers. No larger number divides both.

Extended Euclidean Algorithm

The basic version gives you the GCD. The extended version gives you the GCD and the coefficients for Bézout's identity: ax + by = GCD(a, b).

You get the x and y values for free while working backwards through the steps. Useful when you need modular multiplicative inverses for RSA encryption or Chinese Remainder Theorem problems.

How to Implement It

Iterative Version (Most Common)

function gcd(a, b) {
    while (b !== 0) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

This is the version you'll use 95% of the time. Clean, fast, and uses constant space.

Recursive Version

function gcd(a, b) {
    if (b === 0) return a;
    return gcd(b, a % b);
}

Shorter code. Same result. Slight overhead from function calls, but for most applications this doesn't matter.

Extended Euclidean Version

function extendedGcd(a, b) {
    if (b === 0) return [a, 1, 0];
    let [gcd, x1, y1] = extendedGcd(b, a % b);
    let x = y1;
    let y = x1 - Math.floor(a / b) * y1;
    return [gcd, x, y];
}

Returns [gcd, x, y] where ax + by = gcd.

Comparing GCD Methods

The Euclidean algorithm wins on complexity. For two 100-digit numbers, listing divisors is impossible. This method finishes in microseconds.

Applications

• Cryptography: RSA key generation uses GCD to find coprime numbers
• Simplifying fractions: Divide numerator and denominator by GCD
• Computer graphics: Aspect ratio calculations
• Music theory: Finding the greatest common divisor of note frequencies
• Puzzle solving: Coin denominations, gear ratios, scheduling conflicts

Common Pitfalls

• Forgetting to handle negative numbers — GCD is always non-negative
• Not checking for zero — GCD(a, 0) = |a|
• Using floating-point modulo when you need integer — use % not /

The Bottom Line

You have two numbers. You need their GCD. Use the Euclidean algorithm. It's fast, it's simple, and it's been the standard for two millennia because it works.