Problems with HCF and LCM

HCF or LCM?

The hardest part of a word problem is to choose. Ask what the answer must be.

• The largest size that fits exactly into some amounts (the longest rope piece, the biggest tile, the largest container): the answer divides each amount. Use the HCF.
• The first time that things happen together again (bells, lights, buses, laps): the answer is a multiple of each time. Use the LCM.

A quick check: an HCF answer is never more than the smallest number in the problem. An LCM answer is never less than the largest one.

Bells that ring together

Three bells ring every $15$, $20$ and $24$ minutes. They ring together at $7{:}00$ a.m. When do they next ring together?

1. Choose. They ring together after a time that is a multiple of $15$, $20$ and $24$. We want the first one: the LCM.
2. Factorise. $15 = 3 \times 5$, $20 = 2^2 \times 5$, $24 = 2^3 \times 3$.
3. LCM. $2^3 \times 3 \times 5 = 120$ minutes, that is $2$ hours.
4. Answer the question. They next ring together at $9{:}00$ a.m.

The largest square tile

A floor is $450\ \text{cm}$ long and $330\ \text{cm}$ wide. It must be covered with equal square tiles, with no tile cut. What is the largest tile, and how many tiles are needed?

1. Choose. The side must divide both $450$ and $330$, and it must be as large as possible: the HCF.
2. Factorise. $450 = 2 \times 3^2 \times 5^2$ and $330 = 2 \times 3 \times 5 \times 11$.
3. HCF. $2 \times 3 \times 5 = 30\ \text{cm}$.
4. Count. $\dfrac{450}{30} = 15$ tiles along the length and $\dfrac{330}{30} = 11$ along the width, so $15 \times 11 = 165$ tiles.

When there is a remainder

Some problems leave something over. Take it away (or add it) first.

• The largest number that divides $64$ and $99$ and leaves remainders $4$ and $3$. It divides $64 - 4 = 60$ and $99 - 3 = 96$ exactly. HCF$(60, 96) = 12$.
• The smallest number that leaves a remainder of $1$ when divided by $4$, $6$ and $9$. One less than it is a multiple of all three. LCM$(4, 6, 9) = 36$, so the number is $37$.

Big numbers: Euclid's division method

Factorising $1071$ and $462$ by hand is slow. More than two thousand years ago, Euclid found a faster way. It rests on one fact.

If $a = b \times q + r$, then the HCF of $a$ and $b$ equals the HCF of $b$ and $r$.

Why? Any number that divides $a$ and $b$ also divides $r = a - b \times q$. And any number that divides $b$ and $r$ also divides $a$. So the two pairs have the same common factors.

So divide, keep the divisor and the remainder, and divide again. Stop at a remainder of $0$. The last divisor is the HCF.

• $1071 = 462 \times 2 + 147$
• $462 = 147 \times 3 + 21$
• $147 = 21 \times 7 + 0$

The HCF of $1071$ and $462$ is $21$. Three short divisions did the work.

Try it in Python

The program writes out each step of Euclid's method, then checks the answer with math.gcd, which Python keeps ready for you.

Practise with new numbers

Common mistakes

• Choosing the wrong one. "Largest piece" needs the HCF. "Together again" needs the LCM. Ask whether the answer divides the numbers or is a multiple of them.
• Mixed units. Change $4.5\ \text{m}$ and $330\ \text{cm}$ into the same unit before you find the HCF.
• Stopping at the number. If the question asks for a clock time or a number of tiles, finish that step too.
• Dividing the wrong way in Euclid's method. Always divide the larger number by the smaller one, then the divisor by the remainder.

Remember these

• Largest equal size that fits exactly: HCF. First time together again: LCM.
• With a remainder, take it away from the numbers (for an HCF problem) or add it to the LCM.
• Euclid: $a = b \times q + r$ gives HCF$(a, b) =$ HCF$(b, r)$. The last divisor before the remainder $0$ is the HCF.
• In Python, math.gcd(a, b) gives the HCF.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. A florist has $48$ roses and $72$ lilies. She makes the largest bunches she can, all the same size, each of one kind of flower. How many flowers are in each bunch, and how many bunches are there?

2. Two lighthouses flash every $10$ seconds and every $14$ seconds. They flash together now. After how many seconds do they flash together again?

3. Use Euclid's method to find the HCF of $196$ and $38$.

4. What is the smallest whole number greater than $1$ that leaves a remainder of $1$ when divided by $2$, $3$, $4$, $5$ and $6$?