Highest Common Factor of small integers

Let’s list all the factors of 12 and of 8:

Factors of 12 are: 1, 2, 3, 4, 6, 12

Factors of 8 are: 1, 2, 4, 8

By examining the lists, the highest factor common to both integers 4.

This kind of search is known as an exhaustive search – we list all the factors so all possible values are considered. For small numbers, this is a fast approach especially if it can be done mentally. For large numbers, it can be better to use the prime factor method.

Lowest Common Multiple of small integers

Let’s find the lowest common multiple of 15 and 18.

Of course, the number $270$ which is $15 \times 18$ is a common multiple of 15 and of 18. However, it is not the lowest common multiple.

Multiples of 15 are: 15, 30, 45, 60, 75, 90, 105, 120, …

Multiples of 18 are: 18, 36, 54, 72, 90, good, we can stop here.

The first multiple that we come to that is common to both is 90.

This method is good when the numbers are relatively small.

Practice finding HCF and LCM of small integers

Practice finding the HCF and the LCM by recalling multiplication tables.

Highest Common Factor using the prime factor method

Example 1: Let’s find the HCF of 24 and 30 using the prime factor method.

$24=2 \times 2 \times2 \times 3$

$30=2 \times 3 \times 5$

Prime factors common to both 24 and 30 are 2 and 3. Therefore $2\times 3=6$ is the HCF of 24 and 30.

Example 2: Let’s see how this works with much larger values:

$360=2^3 \times 3^2 \times 5 =2 \times 2 \times 2 \times 3 \times 3 \times 5$

$400 = 2^4 \times 5^2 = 2 \times 2\times 2 \times 2 \times 5 \times 5$

Common to both: $2, 2, 2, 5$

That is, HCF of 360 and 400 is $2\times 2 \times 2 \times 5 = 40$ .

Notice that $360 = 40 \times 9$ ; $400 = 40 \times 10$ . The numbers $9$ and $10$ are known as coprime – they don’t have any common factors.

Lowest Common Multiple Formula

Find the LCM of 15 and 18.

Now, $HCF(15, 18)=3$

Note that:

$18 = 3 \times 6$

$15 = 3 \times 5$

Therefore,

$18 \times 15 = 3 \times 6 \times 3 \times 5$

Let’s divide both sides by 3, the highest common factor:

$\begin{align*}\dfrac{18 \times 15}{3 }&=\dfrac{3 \times 6 \times 3 \times 5}{3}\\[10pt]\dfrac{18 \times 15}{3 }&=6 \times 3 \times 5\end{align*}$

We can be sure that $6 \times 3 \times 5$ is a multiple of both $15$ and $18$ (it is $6 \times 15$ and $5 \times 18$ ). We can also be sure that it is the lowest common multiple as 5 and 6 do not share any factor other than 1.

This leads to the formula:

$LCM(m,n)=\frac{m \times n}{HCF(m,n)}$

Therefore

$LCM(15,18)=\frac{15 \times 18}{3}=90$

Practice finding HCF and LCM of larger integers

Use the prime factor method to find the HCF of the two numbers given. Then use the formula or otherwise to find the LCM.

Top BC G10 Menu Number and Algebra Menu