GCD and LCM Calculator
Find the greatest common divisor and least common multiple of any numbers.
What Is the GCD and LCM Calculator?
The greatest common divisor and the least common multiple are the two answers to opposite questions about a pair of numbers. The GCD asks for the largest number that divides both without a remainder. The LCM asks for the smallest number that both divide without a remainder. They are connected by a clean identity: multiplied together they always equal the product of the inputs, which is a free way to check any answer by hand. This calculator accepts any number of values rather than just two, shows the prime factorisation of each, and reports whether the first two are relatively prime. The GCD is found by the Euclidean algorithm, which is remarkable for how simple it is: you keep replacing the larger number with the remainder of dividing the larger by the smaller, and the answer falls out when the remainder reaches zero.
Key Statistics
-
Euclid, Book X
The greatest common divisor of two numbers is computed by the Euclidean algorithm, which Euclid presented in around 300 BC in the tenth book of the Elements. It is one of the oldest algorithms still in everyday use and appears in the GCD function of every programming language.
Source: Euclid's algorithm, Wikipedia
-
2, 3, 5, 7, 11, 13...
Primes have a greatest common divisor of 1 with every other prime, which is why distinct primes are always relatively prime. Two numbers are relatively prime exactly when their GCD is 1, and this is what makes fractions in lowest terms irreducible.
Source: Relatively prime, Wikipedia
-
10! = 3,628,800
The least common multiple of the whole numbers 1 to 10. It equals the product of each distinct prime to the power of its largest exponent below 10, which gives 2^8 x 3^4 x 5^2 x 7 = 3,628,800, and is why LCM rather than multiplication is used when counting possible outcomes.
Source: Least common multiple, Wikipedia
The Formula
The GCD is found by the Euclidean algorithm: repeatedly replace the larger number with the remainder of dividing the larger by the smaller, until the remainder is zero, and the last non zero value is the GCD. The LCM is the product divided by the GCD, which is computed as (first value divided by GCD) times the second to avoid intermediate overflow.
Worked Examples
For 12 and 18, divide 18 by 12 to get a remainder of 6. Divide 12 by 6 to get a remainder of 0, so the GCD is 6. The LCM is 12 divided by 6, which is 2, times 18, which is 36. As a check, 6 times 36 is 216, which equals 12 times 18.
GCD of 12 and 18 by repeated division
- Divide 18 by 12, which leaves a remainder of 6.
- Divide 12 by 6, which leaves a remainder of 0.
- The last non zero remainder is 6, so the GCD is 6.
- Check: 12 divided by 6 is 2 and 18 divided by 6 is 3, both whole numbers.
GCD: 6
LCM of 4 and 6
- The GCD of 4 and 6 is 2.
- Divide the first number by the GCD: 4 divided by 2 is 2.
- Multiply by the second number: 2 times 6 is 12.
- Check: 12 divided by 4 is 3 and 12 divided by 6 is 2, both whole numbers, and nothing smaller is.
LCM: 12
GCD of three numbers
- Take 48, 18 and 30.
- GCD of 48 and 18 is 6.
- GCD of 6 and 30 is 6.
- So the GCD of all three is 6, which divides 48, 18 and 30 exactly.
GCD: 6
Checking a result with the identity
- Take 9 and 12, whose GCD is 3 and LCM is 36.
- Multiply the GCD and the LCM: 3 times 36 is 108.
- Multiply the original numbers: 9 times 12 is 108.
- The two agree, so both answers are correct.
3 x 36 = 108 = 9 x 12
Real World Use Cases
Simplifying fractions
Dividing the numerator and denominator by their GCD reduces a fraction to lowest terms. For 18 over 24 the GCD is 6, and dividing both by 6 gives the equivalent and much simpler 3 over 4.
Scheduling repeated events
If one bus arrives every 12 minutes and another every 18 minutes and both leave at 9am, the LCM of 12 and 18 is 36, so both together arrive together again 36 minutes later. Buses are a common real example of exactly this.
Packaging and tile sizes
The largest square tile that fits evenly along both dimensions of a room is the GCD of the two lengths. For a 48 by 30 floor the largest square that tiles it without cutting is 6 units on a side.
Lattice points in a rectangle
The number of whole lattice points inside a rectangle with integer sides equals the GCD of the sides plus one. This turns a counting problem into a single division, and is a standard step in many proofs.
Expert Tips
- ✓ Always check your answer with the identity that GCD times LCM equals the product. It costs one multiplication and catches almost every mistake.
- ✓ Compute the LCM as first divided by GCD, times second, rather than product divided by GCD. Dividing first avoids an intermediate number that may be far larger than the answer.
- ✓ Fold several numbers together one at a time, since GCD and LCM of a list are built pairwise. Never try to divide all of them at once.
- ✓ Factorise when the numbers are large or the pattern is obvious. Pairing the prime powers gives the GCD by taking the minimum of each and the LCM by taking the maximum.
- ✓ Two numbers are relatively prime exactly when their GCD is 1, which is the fastest test for whether a fraction can be reduced further.
Frequently Asked Questions
What is the greatest common divisor? ▼
The largest whole number that divides two or more numbers with no remainder. For 12 and 18 it is 6, since 6 divides both exactly and no larger shared divisor exists.
How do I find the GCD? ▼
Use the Euclidean algorithm. Repeatedly divide the larger number by the smaller and keep the remainder, until the remainder is zero. The last non zero value is the GCD. For 18 and 12 the remainders are 6 then 0, so the GCD is 6.
What is the least common multiple? ▼
The smallest whole number that is a multiple of every number given. For 4 and 6 it is 12, because 12 is the first number both divide exactly, since 4 does not divide 6.
How do I calculate the LCM? ▼
Divide the first number by their GCD, then multiply by the second. For 4 and 6 the GCD is 2, so 4 divided by 2 is 2, and 2 times 6 is 12. Dividing before multiplying avoids a much larger intermediate number.
What is the relationship between GCD and LCM? ▼
Their product always equals the product of the original numbers. For 12 and 18, the GCD of 6 and the LCM of 36 multiply to 216, which is 12 times 18. This makes an excellent check on any answer.
What does relatively prime mean? ▼
Two numbers are relatively prime when their GCD is 1, meaning the only number dividing both is 1. Distinct prime numbers are always relatively prime, which is why 8 and 15 share no factor beyond 1.
Can I use more than two numbers? ▼
Yes. Enter as many as you like and they are folded together one at a time. The GCD of 48, 18 and 30 is 6, found by taking the GCD of 48 and 18 first and then combining that with 30.
What happens if a zero is included? ▼
The GCD becomes the other numbers unchanged, since every number divides zero, and the LCM becomes zero, since zero is a multiple of every number. This is a valid result rather than an error.
How is a fraction reduced to lowest terms? ▼
Divide the numerator and denominator by their GCD. For 18 over 24 the GCD is 6, and 18 divided by 6 is 3 while 24 divided by 6 is 4, giving 3 over 4, which cannot be reduced further.
Why does the LCM sometimes come back as too large? ▼
Because the result exceeds the largest integer JavaScript represents exactly, which is over 9 quadrillion. Rather than return a number with digits quietly rounded off, this calculator says so, since a plausible but wrong large number is worse than an honest limit.
Common Mistakes to Avoid
- ⚠ Computing the LCM as the product divided by the GCD without dividing first, which overflows for large inputs.
- ⚠ Giving the smallest common divisor instead of the greatest, which is almost always just 1.
- ⚠ Forgetting that the LCM of a list is built by folding pairwise rather than by dividing the total product by the GCD of the list.
- ⚠ Treating a decimal entry as zero rather than ignoring it, which silently produces a wrong answer.
- ⚠ Expecting the LCM to relate to the sum rather than the product, a common slip when the numbers are small.
Related Tools & Comparisons
Last updated: · by CalculatorPro Tools