🔗 GCD/LCM Calculators

Greatest Common Divisor (GCD)

The Greatest Common Divisor (GCD) of two integers is the largest positive integer that divides both without a remainder. Also called the Greatest Common Factor (GCF) or Highest Common Factor (HCF), it is foundational to fraction simplification: to reduce a/b to lowest terms, divide both numerator and denominator by GCD(a, b). For example, 48/36 reduced: GCD(48,36) = 12, so 48/36 = 4/3. The GCD can be found by listing all factors of each number and identifying the largest common one, or more efficiently using the Euclidean algorithm. Two numbers whose GCD is 1 are called coprime or relatively prime — they share no common factors other than 1. Consecutive integers are always coprime.

The Euclidean Algorithm

The Euclidean algorithm, described by Euclid around 300 BCE, is one of the oldest algorithms still in common use. It computes GCD(a, b) by repeatedly applying: GCD(a, b) = GCD(b, a mod b), stopping when the remainder is 0. Example: GCD(252, 105) → GCD(105, 42) → GCD(42, 21) → GCD(21, 0) = 21. This is dramatically faster than factoring both numbers, especially for large inputs. The extended Euclidean algorithm also finds integers x and y such that ax + by = GCD(a, b) — this is Bezout's identity, and the coefficients x, y are used to compute modular inverses in RSA encryption and other cryptographic applications.

Least Common Multiple (LCM)

The Least Common Multiple (LCM) of two integers is the smallest positive integer that is divisible by both. LCM is used when finding a common denominator for adding or subtracting fractions: to add 1/4 + 1/6, find LCM(4,6) = 12, then rewrite as 3/12 + 2/12 = 5/12. The LCM can be computed from the GCD using the relationship: LCM(a, b) = |a × b| ÷ GCD(a, b). This formula is efficient because it leverages the already-computed GCD. For multiple numbers, apply pairwise: LCM(a, b, c) = LCM(LCM(a, b), c). LCM also arises in scheduling problems — if event A repeats every 4 days and event B every 6 days, they coincide every LCM(4,6) = 12 days.

Coprimality and Its Applications

Two integers are coprime (relatively prime) if GCD(a, b) = 1. Coprimality is important in number theory and has practical applications in cryptography and computer science. Euler's totient function φ(n) counts the integers from 1 to n that are coprime to n — for a prime p, φ(p) = p − 1, since all integers from 1 to p−1 are coprime to p. The Chinese Remainder Theorem states that a system of congruences x ≡ aᵢ (mod mᵢ) has a unique solution modulo M = m₁×m₂×...×mₖ when the moduli are pairwise coprime. This is used in fast modular arithmetic, distributed computing, and the construction of hash functions. In gear design, using coprime tooth counts ensures every tooth on one gear eventually contacts every tooth on the other, distributing wear evenly.