GCD & LCM Calculator

The greatest common divisor simplifies fractions, and the least common multiple finds common denominators and tells you when repeating events line up. Enter two or more whole numbers and this tool gives both, along with each number's prime factorisation so you can see why the answers come out as they do.

How to use it

1. Enter whole numbers separated by commas, spaces or new lines.
2. Read the GCD and LCM.
3. Look at the prime factors of each number.
4. Copy what you need.

When it helps

• Simplifying fractions.
• Finding a common denominator.
• Working out when two repeating schedules coincide.
• Number theory homework.

Good to know

• You can enter up to 30 numbers, all positive whole numbers.
• Very large numbers are handled exactly, though numbers that big may be too long to factorise.
• The LCM is always at least as big as the largest number you enter.

How the answers are found

The GCD is computed with Euclid's algorithm, one of the oldest in mathematics: repeatedly replace the larger number with the remainder of dividing the two until the remainder is zero. The LCM then comes from the identity that the LCM of two numbers equals their product divided by their GCD.

For several numbers, the tool applies the process one pair at a time.

Worked example: 12 and 18

The factors of 12 are 2, 2 and 3, and the factors of 18 are 2, 3 and 3. The GCD takes what they share, 2 times 3, which is 6. The LCM takes the highest power of each prime, 2 squared times 3 squared, which is 36.

That means 12/18 simplifies by dividing both by 6 to 2/3, and 36 is the smallest number both divide into.

Where you'll use it

Fractions are the obvious case: the GCD simplifies and the LCM gives common denominators. Scheduling problems use the LCM: two buses leaving every 12 and 18 minutes leave together every 36. Tiling problems use the GCD: the biggest square tile for a 12 by 18 floor is 6 by 6.

Cryptography also relies on these ideas, particularly with very large numbers.

Prime factorisation

Every whole number above 1 is a product of primes in exactly one way, which is the fundamental theorem of arithmetic. The tool shows these factors with exponents, such as 2 squared times 3. Very large numbers can take a long time to factor, so the tool skips numbers with more than 18 digits.

Spotting shared primes by eye is a good way to check the GCD.

Checking your work by hand

To verify a GCD, divide both numbers by it and check the results share no further factor. To verify an LCM, check it divides evenly by each of your numbers, and that half of it (or any smaller common multiple) doesn't.

For two numbers a and b, the product of their GCD and LCM always equals a times b, which makes a quick sanity check.

Questions