Factors, multiples and the two answers
A factor of a number divides it with no remainder; a multiple is what you get by multiplying it by a whole number. The two results on this page sit on opposite sides of those ideas:
- The greatest common factor (GCF) is the largest number that divides every number in your list. It goes by several names: greatest common divisor (GCD) in most math and programming texts, and highest common factor (HCF) in many British and Commonwealth classrooms. They all mean the same thing.
- The least common multiple (LCM) is the smallest positive number that every number in your list divides into. Some schools call it the lowest common multiple.
The GCF can never be larger than the smallest number in the list, and the LCM can never be smaller than the largest. When the GCF is 1, the numbers are called coprime: 8 and 15 share no factor but 1, and their LCM is simply 8 × 15 = 120.
The Euclidean algorithm
Listing every factor works for small numbers but becomes slow quickly. The method recorded by Euclid more than two thousand years ago is still the standard one, and it is how the calculator finds the GCF: replace the larger number by the remainder after dividing it by the smaller, and repeat until the remainder is 0. The last nonzero remainder is the GCF.
It works because any number that divides both a and b also divides a minus any multiple of b, so each step keeps the same common factors while the numbers shrink. For a list longer than two, the calculator takes the GCF of the first two, then of that result and the third number, and so on.
The last identity holds for exactly two numbers. For three or more, the product of the GCF and the LCM is usually smaller than the product of the numbers. The calculator accepts positive whole numbers of up to 15 digits each, separated by commas or spaces, and keeps every digit, so neither answer is rounded. Prime factorizations are listed for numbers of up to 12 digits; above that, finding them by trial division would slow the page down.
The prime factorization method
Every whole number above 1 is a product of primes in exactly one way, apart from the order of the factors. Writing each number as primes makes both answers visible at once:
- GCF: take each prime that appears in every number, with the smallest power it has in any of them.
- LCM: take every prime that appears anywhere, with the largest power it has in any of them.
| Number | Prime factorization |
|---|---|
| 12 | 2² × 3 |
| 18 | 2 × 3² |
| 30 | 2 × 3 × 5 |
| GCF | 2 × 3 = 6 |
| LCM | 2² × 3² × 5 = 180 |
Under the GCF and LCM, the calculator writes out the prime factorization of each number you enter, with powers shown as 2^2 for 2², so you can follow this method by eye. It finds the primes by trial division, which is quick for numbers of everyday size.
Worked examples
- 1071 = 2 × 462 + 147, so continue with 462 and 147.
- 462 = 3 × 147 + 21, so continue with 147 and 21.
- 147 = 7 × 21 + 0. The remainder is 0, so the GCF is 21.
- LCM = 1071 × 462 ÷ 21 = 494,802 ÷ 21 = 23,562.
- Check with primes: 1071 = 3² × 7 × 17 and 462 = 2 × 3 × 7 × 11. The shared part is 3 × 7 = 21.
- GCF of 84 and 126: 126 = 1 × 84 + 42, then 84 = 2 × 42 + 0, so the GCF is 42.
- Divide top and bottom by 42: 84 ÷ 42 = 2 and 126 ÷ 42 = 3.
- The shared departures happen at common multiples of 12 and 18.
- GCF(12, 18) = 6, so LCM = 12 × 18 ÷ 6 = 36.
- If both leave at 08:00, the next shared departure is 08:36, then 09:12.
Where GCF and LCM are used
The GCF reduces fractions and ratios to lowest terms in one step, and it gives the largest equal groups you can make from several quantities. With 48 red and 180 blue beads, the GCF of 12 means 12 identical bags, each with 4 red and 15 blue.
The LCM gives the least common denominator for adding fractions, and it answers “when do these line up again” questions: repeating timers, rotating shifts, gear teeth meeting the same point, or packs of 24 and 36 items where you want equal totals (72 of each).
Slips with factors and multiples
- Mixing up the two. The GCF is at most the smallest number; the LCM is at least the largest. An answer outside those bounds is the other one.
- Multiplying the numbers to get the LCM. 12 × 18 = 216 is a common multiple, but not the least. Divide by the GCF to get 36.
- Using the two-number identity on three numbers. For 12, 18 and 30, the product is 6,480 while GCF × LCM is 6 × 180 = 1,080.
- Counting 1 as a prime. Prime factorizations start at 2. A GCF of 1 is a valid answer and means the numbers are coprime.
The GCF and LCM are exact for any input the calculator accepts, and the LCM may run to many more digits than the inputs. Trial division is slowest on a 15-digit number whose prime factors are all large, where the factorization can take a moment to appear.
Sources
- Euclid's algorithm, Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology.
- Greatest common divisor, Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology.
- Least common multiple, Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology.
- Prime Factorization, Wolfram MathWorld.