Greatest Common Divisor (GCD)

The Greatest Common Divisor (GCD), also known as the Highest Common Factor (HCF), of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers.

Algorithms for GCD

1. Euclidean Algorithm

The most efficient and common algorithm for computing the GCD is the Euclidean Algorithm. It is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. This process is repeated until one of the numbers becomes zero, at which point the other number is the GCD.

A more efficient version uses the modulo operator:

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

Alternatively, a recursive implementation:

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

2. Brute Force Method (Less Efficient)

This method involves iterating from the minimum of the two numbers down to 1 and checking if each number divides both inputs. The first number found that divides both is the GCD.

function gcdBruteForce(a, b) {
    let smaller = Math.min(a, b);
    for (let i = smaller; i >= 1; i--) {
        if (a % i === 0 && b % i === 0) {
            return i;
        }
    }
    return 1; // Should not reach here if inputs are valid
}
            

This method is generally not recommended for large numbers due to its inefficiency.

Properties of GCD

• gcd(a, b) = gcd(b, a) (Commutativity)
• gcd(a, 0) = |a|
• gcd(a, a) = |a|
• gcd(a, b) = gcd(|a|, |b|)
• gcd(ka, kb) = |k| * gcd(a, b) for any integer k.
• gcd(a, b) = gcd(a - b, b) = gcd(a, b - a)

Applications of GCD

• Simplifying fractions.
• Used in the Extended Euclidean Algorithm to find modular inverses.
• In number theory and cryptography.
• Finding the Least Common Multiple (LCM): lcm(a, b) = (|a| * |b|) / gcd(a, b)

GCD for Multiple Numbers

The GCD of more than two numbers can be found by iteratively applying the GCD function:

gcd(a, b, c) = gcd(gcd(a, b), c)

And for a list of numbers [n1, n2, n3, ..., nk]:

GCD = gcd(n1, gcd(n2, gcd(n3, ..., gcd(nk-1, nk)...)))

function gcdOfList(numbers) {
    if (numbers.length === 0) {
        return 0; // Or throw an error, depending on desired behavior
    }
    let result = numbers[0];
    for (let i = 1; i < numbers.length; i++) {
        result = gcd(result, numbers[i]); // Using the Euclidean algorithm gcd function
    }
    return result;
}