Euclidean Algorithm for GCD

Hello! In our last lesson, we mastered prime factorization, learning how to break down a single integer into its prime building blocks using an efficient O(sqrt(n)) algorithm. We've built a strong foundation in understanding the properties of individual numbers. Now, we'll shift our focus to exploring a fundamental relationship between two integers.

This lesson introduces the Greatest Common Divisor (GCD), which is the largest integer that divides two numbers without leaving a remainder. We'll learn the elegant and highly efficient Euclidean algorithm to compute it. This algorithm is a cornerstone of number theory in competitive programming, not just for its direct use but also as a building block for many other advanced concepts, some of which we'll explore in future lessons.

What is the Greatest Common Divisor (GCD)?

The name says it all. For any two integers, a and b, their Greatest Common Divisor is the largest positive integer that divides both a and b. It's also sometimes called the Highest Common Factor (HCF).

For example, let's find the GCD of 24 and 36.

The divisors of 24 are: {1, 2, 3, 4, 6, 8, 12, 24}
The divisors of 36 are: {1, 2, 3, 4, 6, 9, 12, 18, 36}
The common divisors are: {1, 2, 3, 4, 6, 12}
The greatest of these is 12. So, gcd(24, 36) = 12.

A straightforward way to compute this would be to iterate from min(a, b) down to 1 and return the first number we find that divides both a and b. However, with constraints in competitive programming often going up to 10^12 or even 10^18, an O(min(a, b)) approach is far too slow. We need something much faster.

The following video introduces this exact problem and sets the stage for a more efficient solution.

GCD Algorithms | (Part 1) Euclid's GCD Algorithm | CodeChef Tutorials

This video from CodeChef provides a quick recap of the GCD concept and explains why the naive, brute-force approach is too inefficient for competitive programming.

Watch the section from the recap of GCD to understand the formal definition and the limitations of the brute-force method.

The Euclidean Algorithm: An Elegant Solution

The solution to our performance problem is an ancient and remarkably efficient method called the Euclidean algorithm. It's based on a simple, powerful property:

The greatest common divisor of two numbers a and b is the same as the greatest common divisor of b and the remainder of a divided by b (a % b).

This gives us a recursive formula:
gcd(a, b) = gcd(b, a % b)

A simple visualization of the core recursive step in the Euclidean algorithm. The problem of finding `GCD(a, b)` is reduced to the smaller, equivalent problem of finding `GCD(b, a % b)`.

The process continues until the second number becomes 0. What is the GCD of a number a and 0? Since any number divides 0, the greatest common divisor is simply a itself. This provides our base case: gcd(a, 0) = a.

The CodeChef video you started provides a fantastic explanation of this principle, including the mathematical intuition.

GCD Algorithms | (Part 1) Euclid's GCD Algorithm | CodeChef Tutorials

This part of the video is the core of our lesson. It introduces the recursive formula, explains why it works by connecting it to repeated subtraction, and shows how the modulo operator makes this process incredibly efficient.

First, watch the segment from the algorithm's statement where the recursive relation and base case are formally presented. Next, watch from the proof section. This part gives an intuitive and mathematical justification for a related property, gcd(a, b) = gcd(b, a - b). Finally, see how this connects to the modulo operator in the section from repeated subtraction to modulo. This is the key insight that makes the algorithm so fast.

A Step-by-Step Example

Let's trace the algorithm for gcd(1220, 516). The process unfolds as a chain of simpler, equivalent GCD calculations.

This diagram illustrates the step-by-step application of the Euclidean algorithm to find the GCD of 1220 and 516. Each line reduces the problem to smaller numbers until the remainder is 0, revealing the GCD to be 4.

Following the image, the steps are:

gcd(1220, 516) -> 1220 mod 516 = 188. The problem becomes gcd(516, 188).
gcd(516, 188) -> 516 mod 188 = 140. The problem becomes gcd(188, 140).
gcd(188, 140) -> 188 mod 140 = 48. The problem becomes gcd(140, 48).
gcd(140, 48) -> 140 mod 48 = 44. The problem becomes gcd(48, 44).
gcd(48, 44) -> 48 mod 44 = 4. The problem becomes gcd(44, 4).
gcd(44, 4) -> 44 mod 4 = 0. The problem becomes gcd(4, 0).
We've reached the base case! gcd(4, 0) = 4.

So, the GCD of 1220 and 516 is 4. Notice how quickly the numbers shrink.

C++ Implementation

Given your familiarity with recursion, translating the formula gcd(a, b) = gcd(b, a % b) into C++ is very direct. The cp-algorithms website, a vital resource for competitive programmers, provides a canonical implementation.

Euclidean algorithm for computing the greatest common ...

This article presents the Euclidean algorithm and its implementation, which is standard practice in competitive programming.

Read the section titled Algorithm, and pay close attention to the C++ code in the Implementation section. You will find a recursive, a one-liner ternary, and a non-recursive version. Start with the start of the Algorithm section.

The recursive version is a beautiful, direct translation of the mathematical idea:

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

Or, more compactly with a ternary operator:

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

The iterative (non-recursive) version is also very common in competitive programming to avoid any potential issues with recursion depth limits, though for GCD it's rarely a problem.

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

This version repeatedly swaps a and b while setting a to the remainder, achieving the same result as the recursive calls.

Finally, it's crucial to know that since C++17, a built-in std::gcd function is available in the <numeric> header. In a real contest, you would almost always use this for speed and reliability, but understanding the algorithm behind it is essential for your problem-solving toolkit.

Time Complexity: Why It's So Fast

The Euclidean algorithm is not just elegant; it's also incredibly fast. Its time complexity is O(log(min(a, b))).

This logarithmic complexity means the number of steps required to find the GCD grows very slowly as the input numbers get larger. For example, finding the GCD of two numbers with hundreds of digits takes only a few dozen steps.

The formal proof of this complexity is given by Lamé's theorem, which surprisingly connects the worst-case performance of the algorithm to the Fibonacci sequence. The worst-case inputs are consecutive Fibonacci numbers.

Euclidean algorithm for computing the greatest common ...

This section provides a concise explanation of the algorithm's excellent time complexity.

Read the section Time Complexity to understand why the algorithm is logarithmic. Don't worry about memorizing Lamé's theorem; the key takeaway is the O(log(min(a, b))) complexity and the fact that the numbers shrink exponentially fast.

Conclusion

In this lesson, we've added a powerful and fundamental tool to our number theory arsenal. The Euclidean algorithm is a prime example of how a deep mathematical insight can lead to a solution that is orders of magnitude better than a brute-force approach.

Here are the key takeaways:

The Greatest Common Divisor (GCD) is the largest integer that divides two numbers.
A naive O(min(a, b)) approach is too slow for competitive programming.
The Euclidean Algorithm uses the property gcd(a, b) = gcd(b, a % b) with the base case gcd(a, 0) = a.
It has a very efficient time complexity of O(log(min(a, b))).
You can implement it recursively or iteratively, but for C++17 and later, you should use the built-in std::gcd.

Now that we can efficiently find the GCD, we are ready to tackle its close relative. In our next lesson, we will see how to compute the Least Common Multiple (LCM) of two integers by leveraging the GCD in a simple formula.