How to Find the GCF and LCM
Two quick methods for the greatest common factor and least common multiple, prime factorization and the Euclidean algorithm, with everyday uses from fractions to bus timetables.
The greatest common factor (GCF) and the least common multiple (LCM) are two of the most useful ideas in everyday arithmetic. The GCF helps you split things into equal groups and simplify fractions. The LCM helps you add fractions and work out when repeating events will line up. Both come from the same building blocks: the prime factors of your numbers.
What the two terms mean
- The greatest common factor of a set of numbers is the largest whole number that divides all of them with no remainder. The GCF of 48 and 36 is 12, because 12 goes into both and no larger number does. It is also called the greatest common divisor (GCD) or highest common factor (HCF).
- The least common multiple is the smallest positive number that all of them divide into. The LCM of 12 and 18 is 36: it is in the 12 times table (12, 24, 36) and in the 18 times table (18, 36), and no smaller number is in both.
A quick sanity check: the GCF can never be larger than your smallest number, and the LCM can never be smaller than your largest.
Method 1: prime factorization
Every whole number above 1 can be written as a product of primes in exactly one way. Once you have those products, both answers are easy to read off.
Take 252 and 105.
- 252 = 2² × 3² × 7
- 105 = 3 × 5 × 7
For the GCF, take only the primes that appear in every number, each with its smallest power. Both numbers contain 3 and 7, each at least once, so the GCF is 3 × 7 = 21.
For the LCM, take every prime that appears in any number, each with its largest power: 2² × 3² × 5 × 7 = 4 × 9 × 5 × 7 = 1,260.
This method works well for small numbers and for more than two numbers at once. For 84, 126 and 210:
- 84 = 2² × 3 × 7
- 126 = 2 × 3² × 7
- 210 = 2 × 3 × 5 × 7
The GCF is 2 × 3 × 7 = 42, and the LCM is 2² × 3² × 5 × 7 = 1,260.
Method 2: the Euclidean algorithm
Factoring large numbers by hand is slow. The Euclidean algorithm, which is more than 2,000 years old, finds the GCF without any factoring at all. The rule is: divide the larger number by the smaller one, keep the remainder, and repeat with the smaller number and the remainder until the remainder is zero.
For 252 and 105:
- 252 = 2 × 105 + 42
- 105 = 2 × 42 + 21
- 42 = 2 × 21 + 0
The last non-zero remainder is 21, the same answer as before, in three short steps. It works because any number that divides both 252 and 105 must also divide their difference, and so the remainder.
Getting the LCM from the GCF
For two numbers there is a handy link: GCF × LCM = the product of the two numbers. So:
LCM = a × b ÷ GCF(a, b)
For 252 and 105: 252 × 105 = 26,460, and 26,460 ÷ 21 = 1,260. To avoid huge intermediate numbers, divide first: 252 ÷ 21 = 12, then 12 × 105 = 1,260.
For three or more numbers, work in steps: find the LCM of the first two, then the LCM of that result with the third, and so on. The GCF works the same way.
Everyday uses
Simplifying fractions
To reduce a fraction to its lowest terms, divide the top and bottom by their GCF. For 84/126, the GCF is 42, so 84/126 = 2/3.
Adding fractions
To add fractions with different denominators, you need a common denominator, and the LCM gives the smallest one. For 5/12 + 7/18, the LCM of 12 and 18 is 36. Rewrite as 15/36 + 14/36 = 29/36. Using the plain product 12 × 18 = 216 also works, but leaves you with bigger numbers to simplify.
Cutting and grouping
You want to cut a 48 cm by 36 cm board into equal squares with no waste, as large as possible. The side of the square must divide both lengths, and the largest such number is the GCF, 12 cm. You get 4 × 3 = 12 squares.
The same logic applies to packing: with 48 pencils and 36 erasers, the largest number of identical kits you can make with nothing left over is 12, each holding 4 pencils and 3 erasers.
When things line up again
One bus leaves every 12 minutes and another every 18 minutes. If they leave together at 8:00, they next leave together after the LCM of 12 and 18, which is 36 minutes, at 8:36. The same idea answers questions like when two medication schedules, shift rotations or blinking lights will coincide.
How to use the GCF and LCM Calculator
The GCF and LCM Calculator handles 2 to 50 numbers at once, each up to one trillion:
- Type your whole numbers separated by commas, spaces or new lines.
- Press Calculate.
You get the GCF, the LCM written out in full, and the prime factorization of every number, so you can see exactly which primes are shared. That makes it a good way to check homework done by hand with either method.
Common mistakes
- Mixing up the rules. GCF: common primes, smallest powers. LCM: all primes, largest powers. Swapping "smallest" and "largest" is the most common slip.
- Multiplying instead of finding the LCM. The product of two numbers is a common multiple, but only the least one when the numbers share no factors.
- Stopping the Euclidean algorithm too early. Keep going until the remainder is exactly zero; the answer is the remainder just before that.
- Forgetting that 1 counts. If two numbers share no prime factor, their GCF is 1. That is a real answer, not an error.
FAQ
What does it mean when the GCF is 1?
The numbers are called coprime or relatively prime. For two coprime numbers, the LCM is simply their product: 9 and 16 share no factors, so their LCM is 144.
Is the LCM of two numbers always bigger than both?
Not always. If one number divides the other, the LCM is the larger number itself. The LCM of 6 and 18 is 18.
Can the GCF of two different numbers be one of the numbers?
Yes, when the smaller number divides the larger one exactly. The GCF of 7 and 21 is 7.
Which method should I use by hand?
For small numbers with obvious factors, prime factorization is quick and shows you the structure. For larger numbers, or if you only need the GCF of two numbers, the Euclidean algorithm is faster and needs nothing but division.