GCD and LCM calculator
Greatest common divisor and least common multiple for two or more numbers, with prime factorization and the working shown.
GCD and LCM
Greatest common divisor (GCD)
-
- Least common multiple (LCM)
- -
- Check
- -
Prime factorization
| Number | Prime factors |
|---|
How it works
The GCD (greatest common divisor, also called HCF) is the largest whole number that divides every number in your list with no remainder. The LCM (least common multiple) is the smallest whole number that every number in your list divides into evenly.
- Enter the numbers
Two or more positive whole numbers, separated by commas or spaces.
- Read the GCD and LCM
Both update as you type, along with a check when you enter exactly two numbers.
- See the working
Prime factorization for each number and the Euclidean algorithm steps for the first two.
The Euclidean algorithm
The fastest way to find a GCD by hand repeatedly replaces the larger number with the remainder of dividing it by the smaller one, until the remainder is 0. The last non-zero remainder is the GCD.
gcd(a, b) = gcd(b, a mod b), stopping when the second value is 0
For 18 and 12: 18 = 1 × 12 + 6, then 12 = 2 × 6 + 0, so gcd(18, 12) = 6. For three or more numbers, the calculator combines them two at a time: gcd(a, b, c) = gcd(gcd(a, b), c).
Getting the LCM from the GCD
Once you have the GCD, the LCM of two numbers follows directly: lcm(a, b) = (a × b) / gcd(a, b). For 12 and 18, gcd = 6, so lcm = (12 × 18) / 6 = 36. For more than two numbers, the calculator applies the same rule pairwise: lcm(a, b, c) = lcm(lcm(a, b), c).
What GCD and LCM are used for
- Simplifying fractions: divide the numerator and denominator by their GCD. 12/18 has GCD 6, so it simplifies to 2/3.
- Common denominators: the LCM of the denominators is the smallest common denominator when adding or comparing fractions.
- Scheduling: if one event repeats every 12 days and another every 18 days, they next coincide on day lcm(12, 18) = 36.
- Tiling and packing: the GCD gives the largest square tile that evenly fills a rectangle of given dimensions with no cutting.
Why negative numbers and zero are rejected
GCD and LCM are only defined for positive whole numbers in the usual sense used in school and in software: every number must divide the GCD's own factors, and 0 has infinitely many divisors, so it breaks the definition. Enter positive whole numbers only.
A three-number example and the identity that only works for two
A three-number example shows how the two answers come from the same factorizations. Take 84, 126 and 210.
| Number | Prime factors | Exponents of 2, 3, 7 |
|---|---|---|
| 84 | 2² × 3 × 7 | 2, 1, 1 |
| 126 | 2 × 3² × 7 | 1, 2, 1 |
| 210 | 2 × 3 × 5 × 7 | 1, 1, 1 (and 5 once) |
For the GCD, keep each prime at its smallest exponent across the numbers, and drop primes missing from any number: 2 × 3 × 7 = 42. For the LCM, keep each prime at its largest exponent: 2² × 3² × 5 × 7 = 1260. The Euclidean route agrees: gcd(84, 126) = 42, then gcd(42, 210) = 42. And lcm(84, 126) = 84 × 126 ÷ 42 = 252, then lcm(252, 210) = 252 × 210 ÷ 42 = 1260.
One identity is easy to over-apply. For two numbers, gcd × lcm equals the product of the numbers: 6 × 36 = 12 × 18 = 216. For three or more it does not hold: here 42 × 1260 = 52,920, while 84 × 126 × 210 = 2,222,640.
Two numbers with no shared prime, such as 35 and 64, have a GCD of 1 and an LCM equal to their product, 2,240. That is the situation to expect when a fraction such as 35/64 will not simplify. The Euclidean method stays quick on large inputs: gcd(987, 610), two consecutive Fibonacci numbers and the slowest kind of input for the method, takes 14 division steps, and typical pairs of that size take far fewer.
Frequently asked questions
What is the GCD and how is it calculated?
The GCD is the largest number that divides every number in a set with no remainder. For 12 and 18, the factors of 12 are 1, 2, 3, 4, 6, 12 and the factors of 18 are 1, 2, 3, 6, 9, 18, so the largest common factor is 6. The Euclidean algorithm gets there faster: gcd(18, 12) reduces to gcd(12, 6), then gcd(6, 0), which equals 6.
How is the LCM calculated from the GCD?
For two numbers a and b, lcm(a, b) = (a × b) / gcd(a, b). For 12 and 18, lcm = (12 × 18) / 6 = 216 / 6 = 36. For more than two numbers, the calculator applies it iteratively: lcm(a, b, c) = lcm(lcm(a, b), c). It accepts any number of comma or space separated inputs.
What are GCD and LCM used for in everyday math?
GCD simplifies fractions: divide the numerator and denominator by GCD(numerator, denominator). For 12/18, the GCD is 6, so 12/18 = 2/3. LCM finds the smallest common denominator when adding fractions, and the smallest time when two repeating events coincide again.
Why does the calculator reject negative numbers, zero and decimals?
GCD and LCM are defined for positive whole numbers. A negative or zero input, or a decimal, does not have a well-defined GCD or LCM in the usual sense, so the calculator flags it instead of guessing, and tells you exactly which entries need fixing.
What is prime factorization and how does the calculator use it?
Prime factorization expresses a number as a product of prime powers: 12 = 2² × 3, 18 = 2 × 3². The GCD takes the minimum power of each shared prime: 2¹ × 3¹ = 6. The LCM takes the maximum power of every prime involved: 2² × 3² = 36. The calculator shows the full prime factorization for each number you enter.