Euclid's Algorithm

Introduction

Have you ever needed to find the largest number that divides two numbers exactly?

That number is called the greatest common divisor, usually written as GCD.

Euclid's Algorithm is one of the oldest and most efficient algorithms for finding the GCD of two integers.

Instead of listing all factors of both numbers, the algorithm repeatedly replaces the larger number with the remainder after division.

What is the Greatest Common Divisor?

The greatest common divisor of two numbers is the largest positive integer that divides both numbers without leaving a remainder.

Example:

For 48 and 18:

Factors of 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48
Factors of 18: 1, 2, 3, 6, 9, 18

The common factors are:

1, 2, 3, 6

So:

gcd(48, 18) = 6

How Euclid's Algorithm Works

Euclid's Algorithm is based on this idea:

gcd(a, b) = gcd(b, a % b)

Where % means the remainder after division.

The algorithm follows these steps:

1. Start with two numbers, a and b
2. Divide a by b and get the remainder
3. Replace a with b
4. Replace b with the remainder
5. Repeat until the remainder becomes 0

When b becomes 0, the answer is a.

Step-by-Step Example

Let's find the GCD of 48 and 18.

Step 1: Divide 48 by 18

48 % 18 = 12

So:

gcd(48, 18) = gcd(18, 12)

Step 2: Divide 18 by 12

18 % 12 = 6

So:

gcd(18, 12) = gcd(12, 6)

Step 3: Divide 12 by 6

12 % 6 = 0

Since the remainder is 0, we stop.

The GCD is:

6

Why Does It Work?

If a number divides both a and b, it also divides the difference between them.

The modulo operation is a faster way of repeatedly subtracting b from a.

Example:

48 = 18 x 2 + 12

Any number that divides both 48 and 18 must also divide 12.

That means the GCD does not change when we replace:

gcd(48, 18)

with:

gcd(18, 12)

This process continues until one number divides the other exactly.

JavaScript Implementation

Iterative Version

function gcd(a, b) {
    a = Math.abs(a);
    b = Math.abs(b);

    while (b !== 0) {
        const remainder = a % b;
        a = b;
        b = remainder;
    }

    return a;
}

console.log(gcd(48, 18));

Output:

6

Recursive Version

The same logic can also be written recursively:

function gcd(a, b) {
    a = Math.abs(a);
    b = Math.abs(b);

    if (b === 0) {
        return a;
    }

    return gcd(b, a % b);
}

console.log(gcd(48, 18));

Output:

6

Time Complexity

Euclid's Algorithm is very efficient.

Complexity:

O(log min(a, b))

The numbers become smaller quickly because each step uses the remainder from division.

This makes Euclid's Algorithm much faster than checking all possible divisors one by one.

Common Use Cases

Euclid's Algorithm is commonly used in:

• Simplifying fractions
• Number theory problems
• Competitive programming
• Cryptography
• Computing the least common multiple

Finding the Least Common Multiple

The GCD can be used to find the least common multiple, or LCM.

The formula is:

lcm(a, b) = abs(a x b) / gcd(a, b)

Example:

function gcd(a, b) {
    a = Math.abs(a);
    b = Math.abs(b);

    while (b !== 0) {
        const remainder = a % b;
        a = b;
        b = remainder;
    }

    return a;
}

function lcm(a, b) {
    if (a === 0 || b === 0) {
        return 0;
    }

    return Math.abs(a * b) / gcd(a, b);
}

console.log(lcm(12, 18));

Output:

36

Advantages

• Very efficient
• Easy to implement
• Works with large numbers
• Does not require factorization
• Useful in many mathematical algorithms

Limitations

• Only works directly with integers
• Recursive implementations may hit call stack limits for extremely large inputs
• JavaScript number values can lose precision for very large integers

For very large integers in JavaScript, consider using BigInt.

Final Thoughts

Euclid's Algorithm is a classic example of a simple idea producing a powerful result.

By repeatedly reducing a problem into a smaller equivalent problem, it finds the greatest common divisor quickly and elegantly.

If you are learning algorithms or number theory, Euclid's Algorithm is one of the best algorithms to understand early.

References

Euclidean Algorithm on Wikipedia

Greatest Common Divisor on Wikipedia