1.6 Prime factorisation, HCF and LCM

Prime factorisation

Every whole number greater than 1 can be written as a product of prime numbers, and there is only one way to do it, apart from the order. This is called the unique factorisation theorem. For example, 72 can only be written as 2 \times 2 \times 2 \times 3 \times 3.

Finding prime factors: the factor tree

Split the number into any pair of factors, then keep splitting each factor until every branch ends in a prime. The primes at the ends of the branches are the prime factors.

Worked example. Write 72 as a product of its prime factors.

72 = 8 \times 9, 8 = 4 \times 2, 4 = 2 \times 2, 9 = 3 \times 3. So 72 = 2 \times 2 \times 2 \times 3 \times 3, which in index form is 72 = 2^3 \times 3^2.

You get the same answer whichever factor pair you start with. Another method is the division ladder: divide by the smallest prime that goes in, again and again, until you reach 1.

Worked example (division ladder). Write 180 as a product of prime factors.

180 \div 2 = 90, 90 \div 2 = 45, 45 \div 3 = 15, 15 \div 3 = 5, 5 \div 5 = 1. So 180 = 2^2 \times 3^2 \times 5. Check: 4 \times 9 \times 5 = 180.

HCF and LCM using prime factors

First write each number as a product of primes in index form. For 72 and 60:

72 = 2^3 \times 3^2 and 60 = 2^2 \times 3 \times 5.

• The HCF uses the primes that are in both numbers, each to its lowest power: 2^2 \times 3 = 12.
• The LCM uses every prime that appears in either number, each to its highest power: 2^3 \times 3^2 \times 5 = 360.

Check: HCF × LCM = 12 \times 360 = 4320 and 72 \times 60 = 4320. For two numbers, the product of the numbers always equals HCF × LCM.

HCF and LCM using a Venn diagram

Put the prime factors into a Venn diagram. The factors common to both numbers go in the overlap; the others go in each circle on their own.

The HCF is the product of the numbers in the overlap: 2 \times 2 \times 3 = 12. The LCM is the product of all the numbers in the diagram: 2 \times 2 \times 3 \times 2 \times 3 \times 5 = 360.

Real problems

LCM problems ask when two repeating events happen together.

Worked example. Two lighthouses flash every 12 seconds and every 20 seconds. They flash together at midnight. When do they next flash together?

12 = 2^2 \times 3 and 20 = 2^2 \times 5, so the LCM is 2^2 \times 3 \times 5 = 60. They next flash together after 60 seconds.

HCF problems ask for the largest equal groups, pieces or squares.

Worked example. A floor measures 84 cm by 126 cm. It is covered with identical square tiles with no cutting. What is the largest possible side of a tile, and how many tiles are needed?

84 = 2^2 \times 3 \times 7 and 126 = 2 \times 3^2 \times 7. The HCF is 2 \times 3 \times 7 = 42, so the tiles have side 42 cm. The floor is 84 \div 42 = 2 tiles long and 126 \div 42 = 3 tiles wide, so 6 tiles are needed.

Using prime factors to spot squares

A number is a perfect square if every power in its prime factorisation is even. 72 = 2^3 \times 3^2 has an odd power (3) of 2, so it is not square. Multiplying by 2 gives 2^4 \times 3^2 = 144 = 12^2, a square. So 2 is the smallest number to multiply 72 by to get a square.

Common mistakes

• Giving a list of factors, such as 2, 2, 2, 3, 3, instead of a product: 2 \times 2 \times 2 \times 3 \times 3 or 2^3 \times 3^2.
• Including 1 in a prime factorisation, or using a number that is not prime, such as 4 \times 18.
• Mixing up the rules: HCF takes the lowest powers of the common primes, and LCM takes the highest powers of all the primes.

Exam-style example

Question. (a) Write 150 as a product of prime factors. (b) Find the lowest common multiple of 150 and 90. (c) Hence, or otherwise, state the highest common factor of 150 and 90.

Working. (a) 150 = 2 \times 75 = 2 \times 3 \times 25 = 2 \times 3 \times 5 \times 5 = 2 \times 3 \times 5^2.

(b) 90 = 2 \times 3^2 \times 5. The LCM takes the highest power of each prime: 2 \times 3^2 \times 5^2 = 2 \times 9 \times 25 = 450.

(c) The HCF takes the lowest power of each common prime: 2 \times 3 \times 5 = 30. Check: 150 \times 90 = 13\,500 and 30 \times 450 = 13\,500.

Summary

• Use a factor tree or division ladder to find the prime factorisation.
• Write the answer as a product, in index form if asked.
• HCF: common primes, lowest powers. LCM: all primes, highest powers.
• For two numbers, \text{HCF} \times \text{LCM} = \text{the product of the two numbers}.
• A number is a perfect square when every power in its prime factorisation is even.