GCD & LCM Calculator — Greatest Common Divisor and Least Common Multiple
The greatest common divisor (GCD, also called greatest common factor) of two or more integers is the largest number that divides all of them exactly; the least common multiple (LCM) is the smallest positive number that all of them divide into. This calculator finds both for any list of integers and shows the work: the prime factorization of each number and the step-by-step Euclidean algorithm, so you can follow how the answer was reached, not just copy it.
The two concepts appear constantly in fraction arithmetic. The GCD simplifies a fraction to lowest terms (divide numerator and denominator by their GCD), while the LCM gives the common denominator needed to add or subtract fractions. They are linked by a neat identity — GCD(a, b) × LCM(a, b) = a × b for positive integers — which the calculator uses to compute the LCM efficiently once the GCD is known.
How it works
Euclidean algorithm: GCD(a, b) = GCD(b, a mod b), repeating until the remainder is 0; the last non-zero remainder is the GCD. LCM(a, b) = |a × b| ÷ GCD(a, b). For several numbers, apply pairwise: GCD(a, b, c) = GCD(GCD(a, b), c) and LCM(a, b, c) = LCM(LCM(a, b), c).
Use cases
- Simplifying fractions to lowest terms using the GCD of numerator and denominator
- Finding the least common denominator to add or subtract fractions
- Solving scheduling problems, such as when two repeating events coincide again
- Dividing items into the largest possible equal groups with nothing left over
- Checking homework on prime factorization, GCD, and LCM step by step
- Working out gear ratios or repeating patterns in engineering and music
Frequently asked questions
How do you find the GCD of two numbers?
The fastest method is the Euclidean algorithm: divide the larger number by the smaller, replace the larger with the remainder, and repeat until the remainder is zero — the last non-zero remainder is the GCD. For example, GCD(48, 18): 48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0, so the GCD is 6. This works for numbers of any size without needing factorization.
How do you calculate the LCM using the GCD?
Use the identity LCM(a, b) = |a × b| ÷ GCD(a, b). For 12 and 18, the GCD is 6, so the LCM is 12 × 18 ÷ 6 = 36. For more than two numbers, compute progressively: LCM(a, b, c) = LCM(LCM(a, b), c). This is much faster than listing multiples until one matches.
What is the difference between GCD and LCM?
The GCD is the largest number that divides all the given numbers, so it is always less than or equal to the smallest of them. The LCM is the smallest number that all the given numbers divide, so it is always greater than or equal to the largest of them. In practice, GCD is used to simplify and split into equal groups, while LCM is used to synchronize cycles and find common denominators.
What does it mean when the GCD of two numbers is 1?
It means the numbers are coprime (relatively prime): they share no common factor other than 1. For example, 8 and 15 are coprime even though neither is a prime number. When two numbers are coprime, their LCM equals their product, and a fraction formed by them is already in lowest terms.
How does prime factorization give the GCD and LCM?
Write each number as a product of primes. The GCD takes each common prime raised to the lowest power that appears; the LCM takes every prime that appears raised to the highest power. For 24 = 2³ × 3 and 36 = 2² × 3², the GCD is 2² × 3 = 12 and the LCM is 2³ × 3² = 72. The calculator displays these factorizations so the result is easy to verify.