Greatest Common Divisor (GCD)¶

The Greatest Common Divisor (GCD) of two or more integers is the largest positive integer that divides each of the integers without a remainder.

Euclidean Algorithm¶

The Euclidean algorithm is an efficient method for computing the GCD of two numbers. It is based on the principle that the GCD of two numbers does not change if the larger number is replaced by its difference with the smaller number.

In a more efficient modular version: \(\text{gcd}(a, b) = \text{gcd}(b, a \mod b)\)

1. Recursive Implementation¶

This follows the mathematical definition directly.

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

2. Iterative Implementation¶

Often preferred to avoid stack overflow for very large computations, although for GCD, the recursive depth is very small (\(O(\log(\min(a, b)))\)).

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

Mathematical Properties¶

• \(\text{gcd}(a, b) = \text{gcd}(b, a)\)
• \(\text{gcd}(a, 0) = a\)
• \(\text{gcd}(a, 1) = 1\)
• LCM Relationship: \(\text{lcm}(a, b) = \frac{|a \times b|}{\text{gcd}(a, b)}\)

Sample Input and Output¶

Input¶

48 18

Output¶

GCD of 48 and 18 is 6

Complexity¶

Applications¶

• Simplifying fractions.
• Fundamental step in RSA cryptography.
• Finding Least Common Multiple (LCM).
• Solving Linear Diophantine Equations.