GCD & LCM Calculator

Mathematical Properties of GCD and LCM

The Greatest Common Divisor (GCD) - also termed the Highest Common Factor (HCF) - is the largest positive integer that divides two or more integers without a remainder. The Least Common Multiple (LCM) is the smallest positive integer divisible by all given integers. These fundamental operations are applied in fraction reduction, clock synchronization, modular arithmetic, and cryptography.

The Euclidean Algorithm for GCD

The Euclidean algorithm, documented by Euclid around 300 BC, computes the GCD of two numbers efficiently without factoring them into primes:

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

The process repeats until the remainder becomes zero; the last non-zero divisor is the GCD.

The Fundamental GCD-LCM Relationship

For any two positive integers $a$ and $b$, the product of their GCD and LCM equals the product of the numbers:

$$\gcd(a, b) \times \text{lcm}(a, b) = a \times b$$ $$\text{lcm}(a, b) = \frac{|a \times b|}{\gcd(a, b)}$$

Calculating GCD and LCM in Code

JavaScript

function gcd(a, b) {
  let x = Math.abs(a);
  let y = Math.abs(b);
  while (y !== 0) {
    const temp = y;
    y = x % y;
    x = temp;
  }
  return x;
}

function lcm(a, b) {
  if (a === 0 || b === 0) return 0;
  return Math.abs(a * b) / gcd(a, b);
}

Python (math module)

import math

a, b = 48, 18
print("GCD:", math.gcd(a, b))  # Output: 6
print("LCM:", math.lcm(a, b))  # Output: 144