GCD & LCM Calculator

The GCD (or HCF — Highest Common Factor) of two or more integers is the largest positive integer that divides all of them without remainder. Examples: GCD(12, 8) = 4; GCD(15, 25) = 5; GCD(7, 13) = 1 (coprime). GCD is used to simplify fractions (divide numerator and denominator by GCD), in RSA encryption, finding least common multiples, and modular arithmetic.

The LCM of two or more integers is the smallest positive integer divisible by all of them. Examples: LCM(4, 6) = 12; LCM(3, 7) = 21; LCM(12, 18) = 36. LCM is used to find common denominators when adding fractions, scheduling repeating events (two buses that come every 15 and 20 minutes meet every LCM(15, 20) = 60 minutes), and in modular arithmetic.

The Euclidean algorithm (300 BC) efficiently computes GCD. gcd(a, b) = gcd(b, a mod b), with gcd(a, 0) = a. Example: gcd(48, 18): 48 = 2×18 + 12; 18 = 1×12 + 6; 12 = 2×6 + 0 → GCD = 6. The algorithm runs in O(log(min(a,b))) time. The binary GCD algorithm (Stein's algorithm, 1967) uses bit operations and is faster on processors without hardware division.

For any two positive integers a and b: GCD(a, b) × LCM(a, b) = a × b. So LCM(a, b) = (a × b) / GCD(a, b). This avoids computing LCM separately. For more than two numbers, compute iteratively: GCD(a, b, c) = GCD(GCD(a, b), c); LCM(a, b, c) = LCM(LCM(a, b), c). This is because GCD and LCM are associative operations.

When GCD(a, b) = 1, the numbers are coprime (or relatively prime) — they share no common factors other than 1. Examples: 8 and 9 are coprime; 15 and 28 are coprime. In number theory, coprime pairs are fundamental: Euler's totient function, RSA key generation (e and φ(n) must be coprime), modular inverses, and the Chinese Remainder Theorem all require coprimality. The fraction a/b is in lowest terms if and only if GCD(a, b) = 1.