embed
X

LCM Calculator - Least Common Multiple

+
Table of contents:
The Least Common Multiple calculator finds the lowest possible whole integer which will be evenly divisible by all the digits entered, going up to six different values in advanced mode. Simply enter two or more values in the calculator and it will tell you the lowest number divisible by both.

	the LCM of {2,3,4} is 12
	the LCM of {3,7} is 21
	the LCM of {5,10,25,100} is 100

The intended application is finding common denominators for fraction operations, though other corner use cases may apply.

How It Works

The LCM calculator is actually based on a model of the Sieve of Eratosthenes. This is an ancient Greek mathematical formula for screening out multiples. Start with any list of the whole integers.

Then start with the number 2, and mark off all multiples of 2 (4,6,8,10…). Do the same with 3 (6,9,12,15…) and so on. What you have left are prime numbers (numbers which cannot be divided by any number but themselves and 1), while numbers with two marks indicate they can be evenly divided by two different numbers.

This is easy to try yourself with a computer print-out and a selection of different colors of highlighter.

Of course, there are simpler algorithms that condense the process. Swiss mathematician Leonhard Euler made a formal proof of the Zeta product formula using  the Sieve of Eratosthenes. In fact, there are a whole set of math operations comprising what is known as "sieve theory," a set of general algorithms used to produce sifted sets of numbers.

Factors and Primes

The converse of the LCM is factoring, in which we take a number and find all of the possible divisors for that number that will leave no division remainder. This is a lot harder than it sounds, as basic trial and error is the most reliable method of doing so, barring a few rules:

	All even numbers are divisible by 2.
	All numbers ending in 5 or 0 are divisible by 5.
	All numbers whose sum of digits is a multiple of 3 are divisible by 3.

So the hard answers are numbers ending in 1, 3, 7, and 9. When you get higher up, you get tricky results like 34,393, which has just two divisors (we never count 1 or the number itself): 211 and 163. You can easily find more numbers like these just by multiplying two primes.

The LCM for 6,599 and 2,311 is 15,250,289, and a factoring of that result does indeed show that those are the only two integers that divide it.

We've strayed into the amazing world of prime numbers this way, a corner of near-continuous mathematical research. Prime numbers are important in the field of cryptography because for huge numbers, it is very fast to multiply two large primes and get the result, but much harder to do the reverse: find the two primes that divide one large number.

Prime numbers are also fascinating because we went for centuries trying to prove that they never end in the set of infinite numbers, yet also grow more sparse the higher you count. Quantifying the likelihood of any given very large number being prime in the most efficient way possible is still an ongoing computer science problem.

LCM Calculator - Least Common Multiple

+
Average Calculator
Factor Calculator
Prime Factorization Calculator
... more