math.wiki
Number › Divisibility and primes › Greatest common factor and least common multiple › Finding them from prime factorizations
Open on the map
Math 6 · 6.NS.B.4

Finding them from prime factorizations

Two clock gears with 72 and 84 teeth turn together. When will a marked tooth sit in its marked gap again, and can you tell without listing a long run of multiples?

You need
Greatest common factor by listingMath 6Least common multiple by listingMath 6Prime factorizationMath 6
Where you are 4 in Greatest common factor and least common multiple
Number9
Divisibility and primes10
Greatest common factor and least common multiple4
Common multiples
Finding them from prime factorizations
Greatest common factor by listingLeast common multiple by listing

When you reach for it

Mirela is restoring an old clock. Two of its gears mesh: one has 12 teeth and the other has 18. She paints a dot on one tooth of the small gear and on the gap of the large gear that the tooth sits in. As the gears turn, teeth pass the meeting point one at a time, the same number on each gear. The two dots meet again only when both gears have made whole turns at the same moment, that is, when the number of teeth that have passed is a multiple of 12 and of 18. The first time is their least common multiple.

12\ \text{teeth}
18\ \text{teeth}
Figure 1A 12 tooth gear meshing with an 18 tooth gear. The marked tooth sits in the marked gap.

Listing multiples settles this pair quickly: 18, 36, and 36 is a multiple of 12. After 36 teeth the small gear has turned 3 times and the large one 2 times.

The next pair in the clock has 72 and 84 teeth. Listing still works, but only at the sixth multiple of 84, and finding their greatest common factor by listing factors means writing out twelve factors of each. With bigger numbers listing becomes slow and easy to get wrong. This lesson finds both numbers straight from the prime factorizations by comparing the powers of each prime. Reach for it when the numbers are large, when they have many factors, or when the factorizations are already in front of you.

The procedure

Part 1: comparing the powers of each prime

Factorize both numbers and line up the primes. A factor tree or a ladder gives

72 = 2^3 \cdot 3^2 \qquad 84 = 2^2 \cdot 3 \cdot 7

Write each prime that appears in either number once, and under it the power of that prime in each number. Writing 3 as 3^1 makes the comparison easier to see.

prime237
in 722^33^2none
in 842^23^17^1
GCF: the smaller2^23^1none
LCM: the greater2^33^27^1

The GCF takes the smaller power of each prime the numbers share. A prime that is missing from one number is left out. So

\text{GCF}(72, 84) = 2^2 \cdot 3 = 12

The LCM takes the greater power of every prime in either number. A prime found in only one number comes in at the power it has there. So

\text{LCM}(72, 84) = 2^3 \cdot 3^2 \cdot 7 = 8 \cdot 9 \cdot 7 = 504

For Mirela’s gears, the dots meet again after 504 teeth have passed. The 72 tooth gear has then turned 504 \div 72 = 7 times and the 84 tooth gear 504 \div 84 = 6 times.

The same comparison can be drawn as two overlapping circles, one for the primes of each number, with every shared copy of a prime placed in the overlap.

2
3
2
2
3
7
72
84
Figure 2The primes of 72 and 84. The shared ones, in the overlap, multiply to the GCF, 2 \cdot 2 \cdot 3 = 12. Everything in the picture multiplies to the LCM, 504.

Why the smaller power. A factor of 72 is built only from the primes of 72: at most three 2s and at most two 3s. It cannot contain a 7, because then 72 would have a factorization with a 7 in it, and a number has only one prime factorization. A factor of 84 has at most two 2s, at most one 3 and at most one 7. A factor of both must obey both lists, so it has at most two 2s (the smaller of three and two), at most one 3, and no 7 at all. The greatest such factor uses everything allowed: 2^2 \cdot 3.

Why the greater power. A multiple of 72 contains the whole factorization of 72, so at least three 2s and two 3s. A multiple of 84 contains at least two 2s, one 3 and one 7. A multiple of both needs at least three 2s (the greater of three and two), at least two 3s and at least one 7. The least such multiple has exactly those and nothing else: 2^3 \cdot 3^2 \cdot 7.

Part 2: the product rule, three numbers, and choosing a method

For two numbers, GCF times LCM is the product. Look at the table again. For each prime, one of the two powers went to the GCF and the other went to the LCM: 2^2 to the GCF and 2^3 to the LCM, 3^1 to the GCF and 3^2 to the LCM. A prime in only one number, like 7, skips the GCF and goes once into the LCM. When both numbers hold the same power, the smaller and the greater are the same and each side gets one copy. Either way, between them the GCF and the LCM hold every prime of both numbers exactly once over, so

\text{GCF}(a, b) \cdot \text{LCM}(a, b) = a \cdot b

Check it: 12 \cdot 504 = 6048 and 72 \cdot 84 = 6048.

The rule is a shortcut. Once the GCF is known, the LCM is the product divided by the GCF, and dividing first keeps the numbers small:

\text{LCM}(72, 84) = \frac{72}{12} \cdot 84 = 6 \cdot 84 = 504

Three numbers. The same comparison works for any count of numbers. A factor of all three may use a prime only if all three contain it, and then at the smallest of the three powers. A multiple of all three needs each prime at the greatest of the powers. The product rule, though, is for two numbers only, and Example 5 shows it failing for three.

Which one the problem asks for. A question about splitting into equal parts, or the largest size that fits evenly into both, asks for the GCF, and the answer can be no larger than the smaller number. A question about two repeating things lining up again, or the smallest number both go into, asks for the LCM, and the answer can be no smaller than the larger number. If an answer breaks that size check, the wrong one was found.

Which method. Listing is quickest when the numbers are small or one divides the other: two or three multiples settle it. Prime factorizations win when the numbers are large or have many factors, when the factorizations are already given, and whenever both the GCF and the LCM are wanted, since one table gives both. The product rule wins when one of the two is already known.

Worked examples

Examples 1 to 3 go with Part 1. Examples 4 to 6 go with Part 2.

Example 1

Both from the factorizations

Find the GCF and the LCM of 126 and 150.

Solution

Factorize each number:

126 = 2 \cdot 3^2 \cdot 7 \qquad 150 = 2 \cdot 3 \cdot 5^2

The primes involved are 2, 3, 5 and 7. Both numbers have 2^1, so the smaller power and the greater power are both 2^1. For 3, the powers are 3^2 and 3^1. The 5 is only in 150 and the 7 only in 126, so neither goes into the GCF.

\text{GCF} = 2 \cdot 3 = 6
\text{LCM} = 2 \cdot 3^2 \cdot 5^2 \cdot 7 = 2 \cdot 9 \cdot 25 \cdot 7 = 3150

Check. 3150 \div 126 = 25 and 3150 \div 150 = 21, so 3150 is a common multiple. And 126 \div 6 = 21 and 150 \div 6 = 25, so 6 is a common factor.

Example 2

When the marks meet again

Isla’s clock has two meshing gears with 40 and 56 teeth, a marked tooth on one sitting in a marked gap on the other. How many teeth pass before the marks meet again, and how many turns has each gear made?

Solution

The marks meet when both gears have made whole turns, so the number of teeth passed must be a multiple of 40 and of 56. The first time is the LCM. Factorize:

40 = 2^3 \cdot 5 \qquad 56 = 2^3 \cdot 7

Both hold 2^3, so the greater power is 2^3. The 5 and the 7 each come from one number.

\text{LCM} = 2^3 \cdot 5 \cdot 7 = 280

After 280 teeth, the 40 tooth gear has turned 280 \div 40 = 7 times and the 56 tooth gear 280 \div 56 = 5 times. The bigger gear turns fewer times, as it should.

Example 3

Large numbers, and no shared prime

(a) Find the GCF and the LCM of 2^4 \cdot 3^2 \cdot 11 and 2^2 \cdot 3^3 \cdot 5. (b) Kwabena’s clock has gears with 45 and 64 teeth. How many teeth pass before a marked tooth is back in its marked gap, and how many turns does each gear make?

Solution

(a) The factorizations are given, so compare powers at once. For 2, the powers are 2^4 and 2^2. For 3, they are 3^2 and 3^3. The 11 and the 5 each belong to one number only.

\text{GCF} = 2^2 \cdot 3^2 = 36
\text{LCM} = 2^4 \cdot 3^3 \cdot 5 \cdot 11 = 16 \cdot 27 \cdot 55 = 23760

The two numbers are 1584 and 540. Nobody would list their multiples to find 23760.

(b) Factorize: 45 = 3^2 \cdot 5 and 64 = 2^6. No prime appears in both, so no prime goes into the GCF, and

\text{GCF}(45, 64) = 1

The LCM takes every prime at its own power, which is simply the product:

\text{LCM}(45, 64) = 2^6 \cdot 3^2 \cdot 5 = 64 \cdot 45 = 2880

After 2880 teeth the 45 tooth gear has turned 64 times and the 64 tooth gear 45 times. In that run the marked tooth reaches the meeting point every 45 teeth, 64 times in all, and it never lands in the same gap twice: that would put both gears back where they had been after a common multiple of 45 and 64 smaller than 2880. So the marked tooth visits every one of the 64 gaps before the pattern repeats. With a shared prime the LCM is smaller, and a tooth meets only some of the gaps.

Example 4

Using the product rule

(a) Freya has found that \text{GCF}(66, 110) = 22. Find \text{LCM}(66, 110) without factorizing again. (b) Hamid knows that the tooth counts of two gears have GCF 6 and LCM 252, and that one gear has 42 teeth. How many teeth has the other?

Solution

(a) The GCF times the LCM is the product, so the LCM is the product divided by the GCF. Divide first:

\text{LCM}(66, 110) = \frac{66}{22} \cdot 110 = 3 \cdot 110 = 330

Check with factorizations: 66 = 2 \cdot 3 \cdot 11 and 110 = 2 \cdot 5 \cdot 11, so the LCM is 2 \cdot 3 \cdot 5 \cdot 11 = 330.

(b) Call the other count n. The product rule says 42 \cdot n = 6 \cdot 252 = 1512, so

n = 1512 \div 42 = 36

Check. 36 = 2^2 \cdot 3^2 and 42 = 2 \cdot 3 \cdot 7. The GCF is 2 \cdot 3 = 6 and the LCM is 2^2 \cdot 3^2 \cdot 7 = 252, both as given.

Example 5

Three gears in a row

Arjun’s clock has three gears in a row: a 24 tooth gear meshes with a 36 tooth gear, which meshes with a 45 tooth gear. Each has a marked tooth. How many teeth pass before all three gears are back where they started at the same moment? Find also the GCF of the three counts, and test whether the GCF times the LCM equals the product of the three numbers.

Solution

Meshing gears move tooth for tooth, so the same number of teeth passes on all three. All three are back at the start when that number is a multiple of 24, 36 and 45. Factorize:

24 = 2^3 \cdot 3 \qquad 36 = 2^2 \cdot 3^2 \qquad 45 = 3^2 \cdot 5

For the LCM take the greatest power of each prime: 2^3, 3^2 and 5^1.

\text{LCM} = 2^3 \cdot 3^2 \cdot 5 = 360

The gears have then turned 360 \div 24 = 15, 360 \div 36 = 10 and 360 \div 45 = 8 times.

For the GCF a prime must be in all three. The 2 is missing from 45 and the 5 from 24 and 36, so only 3 qualifies, at its smallest power 3^1. The GCF is 3.

Now 3 \cdot 360 = 1080, but 24 \cdot 36 \cdot 45 = 38880. The rule fails. With three numbers each prime has three powers; the GCF takes the smallest and the LCM the greatest, and the middle one is lost.

Example 6

Which number, which method

(a) Mirela’s clock has gears with 16 and 24 teeth. How many teeth pass before a marked tooth returns to its marked gap? (b) Arjun has gears with 204 and 228 teeth. He wants to paint marks all round each gear, the same number of teeth apart on both, with the marks spaced evenly round each gear and as far apart as possible. How far apart, and how many marks on each gear?

Solution

(a) Lining up again is an LCM. The numbers are small, so list multiples of the larger: 24, 48. The 24 is not a multiple of 16, but 48 = 16 \cdot 3 is, so the LCM is 48. Factorizing would have been no faster.

(b) The spacing must divide 204 and 228 evenly, and be as large as possible: a GCF. Listing the factors of each means twelve of them, so factorize:

204 = 2^2 \cdot 3 \cdot 17 \qquad 228 = 2^2 \cdot 3 \cdot 19

The shared primes are 2, at the smaller power 2^2, and 3, at the smaller power 3^1. The 17 and the 19 each belong to one number only.

\text{GCF} = 2^2 \cdot 3 = 12

Marks every 12 teeth give 204 \div 12 = 17 marks on one gear and 228 \div 12 = 19 on the other. The size check passes: 12 is no larger than 204.

Boundaries

Whole numbers greater than 1. Only they have prime factorizations. The number 1 has no primes, so \text{GCF}(1, n) = 1 and \text{LCM}(1, n) = n. Zero has no factorization and every number divides it, so the method does not apply to 0.

A missing prime counts as no copies. For the GCF it means the prime is left out; for the LCM it means the other number’s power is used. Forgetting a prime that sits in only one number makes the LCM too small.

When one number divides the other, the smaller is the GCF and the larger is the LCM, because every power in the smaller number is already the smaller power.

The product rule needs exactly two numbers. For three or more, \text{GCF} \cdot \text{LCM} is usually less than the product, as Example 5 showed.

Factorizing is the slow part. For very large numbers, finding the primes can take longer than any other step, and then the Euclidean algorithm finds the GCF without factorizing at all.

Where this goes next

The LCM of two denominators is the least common denominator, the smallest number both denominators go into, which is how fractions with unlike denominators are added. The GCF of a numerator and denominator is the largest number that divides both, so dividing by it puts an equivalent fraction in lowest terms in one step. The comparison of powers rests on one factorization per number, stated in full as the fundamental theorem of arithmetic. And when numbers are too large to factorize, the Euclidean algorithm reaches the GCF by repeated division, after which the product rule gives the LCM.

Exercises

Part 1: from given factorizations

Find the GCF and the LCM of each pair.

  1. 3^2 \cdot 5 and 3 \cdot 5^2 \cdot 7
  2. 2^4 \cdot 3 and 2^2 \cdot 3^3
  3. 3 \cdot 5^2 \cdot 11 and 2 \cdot 5 \cdot 11^2

Part 1: factorize first

Find the GCF and the LCM of each pair.

  1. 28 and 70
  2. 50 and 75
  3. 156 and 234
  4. 35 and 48
  5. 225 and 375

Part 1: gears

  1. Freya’s gears have 44 and 60 teeth. How many teeth pass before a marked tooth is back in its marked gap, and how many turns does each gear make?
  2. Kwabena wants to paint marks round two gears with 105 and 126 teeth, the same number of teeth apart on both, spaced evenly round each gear and as far apart as possible. How far apart are the marks, and how many are on each gear?

Part 2: the product rule

  1. \text{GCF}(26, 91) = 13. Use the product rule to find \text{LCM}(26, 91).
  2. Two numbers have GCF 8 and LCM 336. One of them is 48. Find the other.
  3. Can two whole numbers have GCF 6 and LCM 100? Explain.
  4. Two numbers multiply to 3000 and their GCF is 10. Find their LCM, and give one pair of numbers that fits.

Part 2: three numbers

  1. Find the GCF and the LCM of 20, 36 and 42.
  2. Find the GCF and the LCM of 2^2 \cdot 3^3 \cdot 5, 2^3 \cdot 3 \cdot 5^2 and 2 \cdot 3^2 \cdot 5 \cdot 7.
  3. Isla’s clock has three gears in a row with 12, 28 and 40 teeth. How many teeth pass before all three are back where they started, and how many turns does each make?

Part 2: which number, which method

  1. Hamid’s gears have 10 and 15 teeth. How many teeth pass before a marked tooth returns to its marked gap? Choose a quick method.
  2. Mirela wants evenly spaced marks, the same number of teeth apart and as far apart as possible, on gears with 144 and 160 teeth. How far apart, and how many marks on each?
  3. Arjun’s gears have 25 and 36 teeth. How many teeth pass before the marks meet again, and how many turns does each gear make?

Reasoning

  1. Explain why the GCF uses the smaller power of each shared prime and leaves out a prime that appears in only one of the numbers.
  2. Explain why \text{GCF}(a, b) \cdot \text{LCM}(a, b) = a \cdot b for any two whole numbers greater than 1.
  3. Arjun says the product rule works for 10, 14 and 35. Find their GCF and LCM, test his claim, and explain what goes wrong.
  4. Explain why, when a divides b, \text{GCF}(a, b) = a and \text{LCM}(a, b) = b.
Answers
  1. \text{GCF} = 15, \text{LCM} = 1575. Smaller powers: 3 \cdot 5. Greater powers: 3^2 \cdot 5^2 \cdot 7 = 9 \cdot 25 \cdot 7.
  2. \text{GCF} = 12, \text{LCM} = 432. Smaller powers: 2^2 \cdot 3. Greater powers: 2^4 \cdot 3^3 = 16 \cdot 27.
  3. \text{GCF} = 55, \text{LCM} = 18150. Smaller powers: 5 \cdot 11. Greater powers: 2 \cdot 3 \cdot 5^2 \cdot 11^2 = 6 \cdot 25 \cdot 121.
  4. \text{GCF} = 14, \text{LCM} = 140. 28 = 2^2 \cdot 7 and 70 = 2 \cdot 5 \cdot 7; GCF 2 \cdot 7, LCM 2^2 \cdot 5 \cdot 7.
  5. \text{GCF} = 25, \text{LCM} = 150. 50 = 2 \cdot 5^2 and 75 = 3 \cdot 5^2; GCF 5^2, LCM 2 \cdot 3 \cdot 5^2.
  6. \text{GCF} = 78, \text{LCM} = 468. 156 = 2^2 \cdot 3 \cdot 13 and 234 = 2 \cdot 3^2 \cdot 13; GCF 2 \cdot 3 \cdot 13, LCM 2^2 \cdot 3^2 \cdot 13.
  7. \text{GCF} = 1, \text{LCM} = 1680. 35 = 5 \cdot 7 and 48 = 2^4 \cdot 3 share no prime, so the LCM is the product 35 \cdot 48.
  8. \text{GCF} = 75, \text{LCM} = 1125. 225 = 3^2 \cdot 5^2 and 375 = 3 \cdot 5^3; GCF 3 \cdot 5^2, LCM 3^2 \cdot 5^3.
  9. 660 teeth; the 44 tooth gear turns 15 times and the 60 tooth gear 11 times. 44 = 2^2 \cdot 11 and 60 = 2^2 \cdot 3 \cdot 5, so the LCM is 2^2 \cdot 3 \cdot 5 \cdot 11 = 660.
  10. Every 21 teeth: 5 marks on the 105 tooth gear and 6 on the 126 tooth gear. 105 = 3 \cdot 5 \cdot 7 and 126 = 2 \cdot 3^2 \cdot 7, so the GCF is 3 \cdot 7 = 21.
  11. \text{LCM} = 182. \displaystyle \frac{26}{13} \cdot 91 = 2 \cdot 91.
  12. 56. The other number is 8 \cdot 336 \div 48 = 2688 \div 48.
  13. No. The GCF divides each number and each number divides the LCM, so the GCF must divide the LCM. But 100 \div 6 leaves remainder 4.
  14. \text{LCM} = 300, since 3000 \div 10 = 300. One pair is 30 and 100: their GCF is 10 and their LCM is 300.
  15. \text{GCF} = 2, \text{LCM} = 1260. 20 = 2^2 \cdot 5, 36 = 2^2 \cdot 3^2, 42 = 2 \cdot 3 \cdot 7. Only 2 is in all three, smallest power 2^1; LCM 2^2 \cdot 3^2 \cdot 5 \cdot 7.
  16. \text{GCF} = 30, \text{LCM} = 37800. Smallest powers: 2 \cdot 3 \cdot 5, and 7 is not in all three. Greatest powers: 2^3 \cdot 3^3 \cdot 5^2 \cdot 7.
  17. 840 teeth; the gears turn 70, 30 and 21 times. 12 = 2^2 \cdot 3, 28 = 2^2 \cdot 7, 40 = 2^3 \cdot 5, so the LCM is 2^3 \cdot 3 \cdot 5 \cdot 7 = 840.
  18. 30 teeth. List multiples of 15: 15, 30, and 30 \div 10 = 3.
  19. Every 16 teeth: 9 marks on the 144 tooth gear and 10 on the 160 tooth gear. 144 = 2^4 \cdot 3^2 and 160 = 2^5 \cdot 5, so the GCF is 2^4 = 16.
  20. 900 teeth; the 25 tooth gear turns 36 times and the 36 tooth gear 25 times. 25 = 5^2 and 36 = 2^2 \cdot 3^2 share no prime, so the LCM is 25 \cdot 36.
  21. A common factor divides both numbers, so it may contain a prime only as often as each number does. That caps each prime at the smaller of the two powers, and a prime missing from one number is capped at no copies. The greatest common factor takes every prime up to its cap.
  22. For each prime, the GCF takes the smaller of the two powers and the LCM the greater, so between them they take both powers once each. A prime in only one number goes once into the LCM and not into the GCF. So \text{GCF} \cdot \text{LCM} has exactly the primes of a and b together, which is a \cdot b.
  23. \text{GCF} = 1 and \text{LCM} = 70, so \text{GCF} \cdot \text{LCM} = 70, but 10 \cdot 14 \cdot 35 = 4900. He is wrong. The prime 2 is in 10 and 14: the product holds two 2s, the LCM one, and the GCF none, since 35 has no 2. With three numbers the middle power of each prime is lost.
  24. Every prime of a is in b at a power at least as great, since a divides b. So the smaller powers are exactly those of a, giving \text{GCF} = a, and the greater powers are exactly those of b, giving \text{LCM} = b.
kg1128 · updated 2026-10-12 · CC-BY-SA-4.0