HCF and LCM from Prime Factorisation

Why bother?#

You've found HCF and LCM before by long divi­sion and by list­ing mul­ti­ples, and it can be slow. Once a num­ber is writ­ten as a prod­uct of prime pow­ers, though, its HCF and LCM can be read straight off, with­out a sin­gle divi­sion. Let's see the rule, why it works, and a handy iden­tity that gives you one from the other.

Read­ing HCF and LCM off the fac­tori­sa­tions#

Write both num­bers in prime-power form, lin­ing up the same primes one under the other.

$$168 = 2^3 \times 3 \times 7, \qquad 180 = 2^2 \times 3^2 \times 5$$

• HCF, take each prime that appears in both, with the smaller expo­nent.
• LCM, take each prime that appears in either, with the larger expo­nent.

$$\mathrm{HCF}(168, 180) = 2^2 \times 3 = 12$$
$$\mathrm{LCM}(168, 180) = 2^3 \times 3^2 \times 5 \times 7 = 2520$$

Why the smaller expo­nent for the HCF? A com­mon divi­sor can't use more copies of $2$ than the poorer of the two num­bers owns. $180$ has only $2^2$, so no com­mon divi­sor can con­tain $2^3$.

And why the larger for the LCM? A com­mon mul­ti­ple must con­tain enough copies of $2$ to be divis­i­ble by $168$, and that needs three of them.

The iden­tity#

For any two pos­i­tive inte­gers $a$ and $b$,

$$\mathrm{HCF}(a,b) \times \mathrm{LCM}(a,b) = a \times b$$

Check it on the pair above: $12 \times 2520 = 30240$, and $168 \times 180 = 30240$. They agree.

You can see why by look­ing at the expo­nents. For each prime, one num­ber sup­plies the smaller expo­nent and the other sup­plies the larger. The HCF takes one and the LCM takes the other, so between them they use both, which is exactly what mul­ti­ply­ing $a$ by $b$ does.

A warn­ing: this iden­tity holds for two num­bers only. For three it fails, and it's easy to see: take $2$, $4$ and $8$. Then $\mathrm{HCF} = 2$ and $\mathrm{LCM} = 8$, so $\mathrm{HCF} \times \mathrm{LCM} = 16$, while $2 \times 4 \times 8 = 64$. Quot­ing the iden­tity for three num­bers is a com­mon mis­take, and an expen­sive one in board exams.

Worked exam­ples#

Which one does the ques­tion want?#

Word prob­lems rarely say "HCF" or "LCM" out loud, so you have to decide from what is being asked.

• Cut­ting or shar­ing into equal parts, largest pos­si­ble → HCF. The size must divide every quan­tity.
• Events repeat­ing together, ear­li­est → LCM. The time must be a mul­ti­ple of every inter­val.

Here's a quick test to set­tle it: if the answer must be no larger than the num­bers given, it's an HCF. If it must be no smaller, it's an LCM.

Prac­tice#

1. Find the HCF and LCM of $60$ and $88$ by prime fac­tori­sa­tion, and ver­ify the iden­tity.
2. Given $\mathrm{HCF}(510, 92) = 2$, find $\mathrm{LCM}(510, 92)$ with­out fac­toris­ing either num­ber.
3. Find the HCF and LCM of $12$, $18$ and $30$.
4. Show that $\mathrm{HCF} \times \mathrm{LCM} \ne$ prod­uct, for the three num­bers in ques­tion 3.
5. Rib­bons of length $77$ cm and $121$ cm are to be cut into equal pieces of the great­est pos­si­ble length, with noth­ing left over. Find that length and the num­ber of pieces.

Answers#