chevron_left Highest Common Factor (HCF) chevron_right

Highest Common Factor (HCF)

What Exactly is the Highest Common Factor?

Imagine you have two numbers. Each number can be built by multiplying smaller numbers, which we call its factors. The Highest Common Factor is simply the biggest number that appears in the list of factors for both of your original numbers. For example, the factors of 12 are 1, 2, 3, 4, 6, and 12. The factors of 18 are 1, 2, 3, 6, 9, and 18. The common factors are 1, 2, 3, and 6. The largest of these is 6, so the HCF of 12 and 18 is 6.

Methods for Finding the HCF

There are several reliable ways to find the HCF of two or more numbers. We will explore the three most common methods, starting with the simplest.

1. Listing Factors Method

This is the most straightforward method, perfect for smaller numbers. You list all the factors of each number and then identify the largest one that is common to all lists.

Example: Find the HCF of 24 and 36.

• Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24
• Factors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36
• Common factors: 1, 2, 3, 4, 6, 12
• The Highest Common Factor is 12.

2. Prime Factorization Method

This method is more systematic and works well for larger numbers. It involves breaking down each number into its prime factors^[1]. The HCF is then the product of the smallest power of all common prime factors.

Example: Find the HCF of 60 and 84.

First, find the prime factors:

• $60 = 2^2 \times 3^1 \times 5^1$
• $84 = 2^2 \times 3^1 \times 7^1$

The common prime factors are 2 and 3.

The lowest power of 2 is $2^2$. The lowest power of 3 is $3^1$.

Therefore, $HCF = 2^2 \times 3^1 = 4 \times 3 = 12$.

3. Division Method (Euclidean Algorithm)

This efficient algorithm, named after the ancient Greek mathematician Euclid, is excellent for very large numbers. It is based on the principle that the HCF of two numbers also divides their difference.

Steps:

1. Divide the larger number by the smaller number.
2. Take the remainder from this division.
3. Replace the larger number with the smaller number, and the smaller number with the remainder.
4. Repeat steps 1-3 until the remainder is 0.
5. The divisor at this stage is the HCF.

Example: Find the HCF of 56 and 72.

• Step 1: $72 \div 56 = 1$ with a remainder of $16$.
• Step 2: Now, take 56 and 16. $56 \div 16 = 3$ with a remainder of $8$.
• Step 3: Now, take 16 and 8. $16 \div 8 = 2$ with a remainder of $0$.
• Since the remainder is now 0, the HCF is the last divisor, which is 8.

Finding the HCF of More Than Two Numbers

The methods we've learned can be extended to find the HCF of three or more numbers. The prime factorization method is particularly well-suited for this.

Example: Find the HCF of 18, 24, and 30 using prime factorization.

• $18 = 2^1 \times 3^2$
• $24 = 2^3 \times 3^1$
• $30 = 2^1 \times 3^1 \times 5^1$

The common prime factors across all three numbers are 2 and 3.

The lowest power of 2 is $2^1$. The lowest power of 3 is $3^1$.

Therefore, $HCF = 2^1 \times 3^1 = 6$.

You can also find the HCF of multiple numbers by first finding the HCF of two of them, and then finding the HCF of that result and the next number. For example, $HCF(18, 24) = 6$. Then $HCF(6, 30) = 6$.

HCF in Action: Real-World Applications

The HCF is not just a mathematical exercise; it has practical uses in everyday life and problem-solving.

1. Simplifying Fractions: This is one of the most common applications. The HCF of the numerator and denominator is the number you divide by to reduce a fraction to its simplest form.

Simplify the fraction $\frac{24}{36}$.

We already found that the HCF of 24 and 36 is 12.

$\frac{24 \div 12}{36 \div 12} = \frac{2}{3}$.

2. Distributing Items Equally: Imagine you have 32 pencils and 40 erasers. You want to make identical sets for your friends, with no items left over. What is the greatest number of identical sets you can make?

The number of sets must be a common factor of both 32 and 40. To make the greatest number of sets, you need the HCF.

• HCF of 32 and 40 is 8.

So, you can make 8 sets. Each set would contain $32 \div 8 = 4$ pencils and $40 \div 8 = 5$ erasers.

3. Planning Events: If one event occurs every 12 days and another every 18 days, and they happen together today, the HCF tells you how often they will coincide in the future. The HCF of 12 and 18 is 6, meaning both events will occur together every 6 days.

Common Mistakes and Important Questions

Footnote

^[1] Prime Factors: The factors of a number that are prime numbers. For example, the prime factors of 12 are 2 and 3.

^[2] LCM: Least Common Multiple. The smallest positive integer that is a multiple of two or more numbers.