Four ways to find the HCF and LCM

In Discover you found the HCF and LCM by listing: write out factors or multiples and look for the ones that match. That works well for small numbers. But try listing the multiples of 84 and 126 until they meet, or all the factors of 1,080, and you will soon want something better.

This layer gives you four methods and the reasons they work:

1. Listing factors or multiples: good for small numbers and for seeing the idea.
2. Prime factorisation, with a Venn diagram in your head: the method that shows why.
3. Long division (continued division) for the HCF: fast for big numbers.
4. Common division (the ladder) for the LCM: tidy for three or more numbers.

Along the way you will meet three facts that make HCF and LCM problems much quicker, the classic mix-ups, and the place where all this matters most in school maths: fractions.

Read those definitions slowly, because every word matters.

• "Each" means all of them. A common factor of 12, 18 and 20 must divide all three. 3 divides 12 and 18 but not 20, so it is not a common factor of the three.
• "Exactly" means remainder 0.
• "Positive" in the LCM rules out 0, which is a multiple of every number.
• "Divides" has a direction. "4 divides 12" means 12 ÷ 4 is exact. We sometimes write this as 4 | 12, read "4 divides 12". So HCF(a, b) | a, HCF(a, b) | b, a | LCM(a, b) and b | LCM(a, b).

The order of the numbers never matters: HCF(12, 18) = HCF(18, 12), and the same for LCM.

Listing has two weaknesses.

• It gets slow. LCM(84, 126) = 252. Counting in 126s, you need 2 tries, which is fine. But LCM(84, 125) = 10500: you would need 84 multiples of 125 before one works!
• It is easy to miss a factor. 360 has 24 factors. Miss one and you might miss the HCF.

The next methods build the answer directly, instead of searching for it.

Every whole number bigger than 1 is either prime or can be built by multiplying primes. Its prime factorisation is its recipe:

• 36 = 2 × 2 × 3 × 3 = 2² × 3²
• 48 = 2 × 2 × 2 × 2 × 3 = 2⁴ × 3
• 60 = 2 × 2 × 3 × 5 = 2² × 3 × 5
• 84 = 2 × 2 × 3 × 7 = 2² × 3 × 7

However you split a number, you always end up with the same primes the same number of times. (Split 36 as 4 × 9 or as 6 × 6 or as 2 × 18: you always reach two 2s and two 3s.) This fact, that the recipe is unique, is called the Fundamental Theorem of Arithmetic. It is the reason the prime-factor method for HCF and LCM works, and the Deepen layer explains why it is true.

A common factor of 36 and 48 must be made only from primes that both recipes contain, and it cannot use any prime more times than either recipe has it.

• 36 = 2 × 2 × 3 × 3
• 48 = 2 × 2 × 2 × 2 × 3

Pair up the primes they share: two 2s are in both (36 has only two), and one 3 is in both (48 has only one). The shared primes are 2 × 2 × 3, and their product is 12. That is the HCF.

In index form: 36 = 2² × 3² and 48 = 2⁴ × 3. Take each common prime with its smaller power: 2² × 3¹ = 12.

A common multiple of 36 and 48 must contain the recipe of 36 and contain the recipe of 48. So it needs every prime that appears in either number, each as many times as the greedier number needs it.

• 36 needs two 2s and two 3s.
• 48 needs four 2s and one 3.

The smallest recipe that satisfies both needs four 2s and two 3s: 2⁴ × 3² = 144. That is the LCM.

Rule: LCM = every prime that appears, each with its highest power.

For big numbers, factorising can be hard. Try factorising 391 quickly! The long division method (also called continued division, or Euclid’s algorithm) avoids factorising altogether.

The rule:

1. Divide the bigger number by the smaller one.
2. If the remainder is 0, the divisor is the HCF. Stop.
3. Otherwise, make the old divisor the new dividend and the remainder the new divisor. Go back to step 1.

The last non-zero remainder, which is the last divisor, is the HCF.

Why on earth should this work? Here is the short version: any number that divides both 252 and 198 also divides their difference, and so it also divides the remainder 252 − 198 = 54. So the pair (252, 198) has exactly the same common factors as the pair (198, 54), and the numbers keep shrinking until the answer is obvious. The Deepen layer turns this into a proper argument.

The common division method finds the LCM of several numbers at once. Write the numbers in a row. Divide by a prime that divides at least two of them. Numbers it divides are replaced by the quotient; numbers it does not divide are brought down unchanged. Repeat until no prime divides two of the numbers in the row.

The LCM is the product of all the divisors on the left and all the numbers left in the bottom row.

Many textbooks carry on dividing until every number in the bottom row is 1, even when a prime divides only one number. Both ways give the same LCM; the version above is just shorter.

Every method extends to three (or more) numbers.

• Prime factorisation: for the HCF take the primes common to all three, with the smallest power; for the LCM take every prime that appears in any of them, with the highest power.
• Two at a time: HCF(a, b, c) = HCF(HCF(a, b), c), and LCM(a, b, c) = LCM(LCM(a, b), c). So you can use long division twice.
• Ladder: works directly for the LCM, as you just saw.

Fact 1: HCF × LCM = product of the two numbers. For 12 and 18: HCF = 6, LCM = 36, and 6 × 36 = 216 = 12 × 18. For 36 and 48: 12 × 144 = 1728 = 36 × 48. The Venn picture shows why: the two circles together use every prime of both numbers once, with the overlap counted twice. HCF × LCM also counts the overlap twice (once in the HCF, once in the LCM).

This fact is only for two numbers. For 18, 30 and 42: HCF × LCM = 6 × 630 = 3780, but 18 × 30 × 42 = 22,680. Not equal!

Fact 2: co-primes. If HCF(a, b) = 1, then LCM(a, b) = a × b. (Put HCF = 1 into Fact 1.) Example: LCM(8, 15) = 120.

Fact 3: the HCF always divides the LCM. The HCF divides a, and a divides the LCM, so the HCF divides the LCM. For 36 and 48: 144 ÷ 12 = 12.

This is where most people use HCF and LCM every week without noticing.

Simplifying a fraction uses the HCF. To write 84⁄126 in its simplest form, divide top and bottom by the largest number that divides both, HCF(84, 126) = 42. That gives 2⁄3 in one step. Dividing by a smaller common factor, like 2, also works, but you would have to keep going.

Adding or subtracting fractions uses the LCM. To add 5⁄12 + 7⁄18 you need a common denominator: a common multiple of 12 and 18. The smallest one, LCM(12, 18) = 36, keeps the numbers small. It is called the lowest common denominator.