GCD and LCM Calculator
Enter two or more positive integers separated by commas (up to 1 trillion, 10¹² each). You will see their GCD (Greatest Common Divisor), LCM (Least Common Multiple), the Euclidean algorithm step by step, and the prime factorization method.
Integers from 1 to 10¹² (1,000,000,000,000), up to 6 values.
About GCD and LCM
What is the GCD (Greatest Common Divisor)?
The GCD (also called GCF — Greatest Common Factor, or HCF — Highest Common Factor) of two or more integers is the largest positive integer that divides all of them without a remainder. For example, GCD(48, 180) = 12 because 12 is the largest number that divides both 48 and 180.
What is the LCM (Least Common Multiple)?
The LCM of two or more integers is the smallest positive integer that is divisible by all of them. For example, LCM(48, 180) = 720 because 720 is the smallest multiple shared by both 48 and 180. The LCM is used when adding fractions with different denominators.
Frequently asked questions
GCD (Greatest Common Divisor), GCF (Greatest Common Factor) and HCF (Highest Common Factor) are three names for the same concept: the largest integer that divides two or more numbers exactly. GCD and GCF are common in North America; HCF is widely used in the UK.
The Euclidean algorithm is based on the identity GCD(a, b) = GCD(b, a mod b). Starting from the two numbers, it repeatedly replaces the larger with the remainder of the division, until the remainder is 0. The last non-zero remainder is the GCD. For GCD(48, 180): 180 = 48 × 3 + 36, then 48 = 36 × 1 + 12, then 36 = 12 × 3 + 0, so GCD = 12.
Two integers are coprime (or relatively prime) if their GCD equals 1 — they share no common factor other than 1. For example, 35 = 5 × 7 and 64 = 2⁶ share no prime factors, so GCD(35, 64) = 1 and they are coprime. Coprime pairs are fundamental in modular arithmetic and cryptography (RSA).
For any two positive integers A and B: GCD(A, B) × LCM(A, B) = A × B. This follows from prime factorization: GCD takes the minimum exponent for each prime, LCM takes the maximum, and min(e, f) + max(e, f) = e + f for every prime. The identity lets you compute LCM quickly once you know the GCD: LCM(A, B) = A × B ÷ GCD(A, B).
Apply the Euclidean algorithm iteratively: GCD(a, b, c) = GCD(GCD(a, b), c). The result does not depend on the order. The same principle extends to any count of integers, and this calculator supports up to 6 values at once.