Euclidean Algorithm

Introduction

The Greatest Common Divisor (GCD), or Highest Common Factor (HCF), is a fundamental mathematical concept and an essential algorithm in data structures and competitive programming. Whether it's simplifying fractions, modular arithmetic, or cryptographic systems, GCD plays a vital role in problems involving divisibility.

In this blog, we start from basic methods like brute-force and subtraction, gradually moving toward the highly efficient Euclidean Algorithm, which reduces the time complexity from linear to logarithmic.

What is GCD?

Given two integers a and b, the GCD is the largest integer that divides both without leaving a remainder.

For example:

• GCD(36, 60) = 12

• GCD(49, 14) = 7

• GCD(17, 29) = 1 (co-prime numbers)

Naive Approach: Brute Force

How it Works:

Iterate from 1 to min(a, b), and for each number, check if it divides both a and b. Keep track of the largest such number.

C++ Code

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

Java Code

public static int gcdBruteForce(int a, int b) {
    int gcd = 1;
    for (int i = 1; i <= Math.min(a, b); i++) {
        if (a % i == 0 && b % i == 0)
            gcd = i;
    }
    return gcd;
}

Drawbacks

• Time complexity: O(min(a, b))

• Impractical for large numbers

Subtraction-Based GCD: The Original Euclidean Method

Concept

Instead of checking divisibility, subtract the smaller number from the larger repeatedly until both numbers become equal. That number is the GCD.

This was the original idea of the Euclidean Algorithm before the modulo-based version was discovered.

Example

GCD(48, 18)
→ 48 - 18 = 30
→ 30 - 18 = 12
→ 18 - 12 = 6
→ 12 - 6 = 6
→ 6 - 6 = 0
GCD = 6

C++ Code

int gcdSubtraction(int a, int b) {
    while (a != b) {
        if (a > b)
            a -= b;
        else
            b -= a;
    }
    return a;
}

Java Code

public static int gcdSubtraction(int a, int b) {
    while (a != b) {
        if (a > b)
            a -= b;
        else
            b -= a;
    }
    return a;
}

Complexity

• Time complexity: O(max(a, b))

• Better than brute-force but inefficient for large inputs.

The Euclidean Algorithm: Modulo-Based and Logarithmic

Key Insight:

GCD(a, b) = GCD(b, a % b)

Why does this work?

If a number divides both a and b, it also divides a - b and a % b. This is a fundamental property of divisibility.

Example

GCD (48,18)

48 - 18 = 30
30 - 18 = 12
(=> 48 % 18 = 12)
18 - 12 = 6
(=> 18 % 12 = 6)
12 - 6 = 6
(=> 12 % 6 = 0 ie gcd is 6)
6 - 6 = 0 
hence gcd is same for both methods

So instead of subtracting multiple times, we jump straight to the remainder using the modulo operator.

Recursive Approach

C++ Code

int gcdRecursive(int a, int b) {
    if (b == 0)
        return a;
    return gcdRecursive(b, a % b);
}

Java Code

public static int gcdRecursive(int a, int b) {
    if (b == 0)
        return a;
    return gcdRecursive(b, a % b);
}

Iterative Approach

Some environments (like embedded systems) prefer iteration over recursion to avoid stack overflow.

C++ Code

int gcdIterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

Java Code

public static int gcdIterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

Time and Space Complexity

Special Case Handling

LCM from GCD

Note: In maths, we all know the formula

hcf(gcd) * lcm = product of two numbers

By using the same formula, we will find the lcm of two numbers. So,

LCM(a, b) = (a / GCD(a, b)) * b

C++ Code

int lcm(int a, int b) {
    return (a / gcdIterative(a, b)) * b;
}

Java Code

public static int lcm(int a, int b) {
    return (a / gcdIterative(a, b)) * b;
}

Conclusion

The Euclidean Algorithm is not just an efficient way to find the GCD; it represents the evolution of mathematical thought from simple iteration to optimized recursion. By reducing the size of inputs logarithmically, it delivers incredible performance even for large numbers.

If you're preparing for coding interviews, math contests, or competitive programming, mastering this algorithm is non-negotiable. It's simple, powerful, and incredibly useful across domains.

For more such content click here

Till then,

Happy Coding