What is the highest common factor?

What is the highest common factor?

The HCF (highest common factor) of numbers is the largest factor that goes into both/all numbers.

For example, the HCF of 12 and 15 is 3, because 3 is the largest number that goes into both 12 and 15.

Finding the highest common factor

To find the highest common factor, you need to be familiar with prime factor decomposition.

Here are the steps:

  1. Find the prime factor decomposition of each number.
  2. Find the common prime factors (and how many of each there are)
  3. Multiply the common prime factors together to get the HCF

Example: Find the HCF of 18 and 24.

  1. Find the prime factor decomposition of each number:
    • 18 = 2 \times 3 \times 3 = 2 \times 3^2
    • 24 = 2 \times 2 \times 2 \times 3 = 2^3 \times 3
  2. Find the common prime factors:
    • Both have at least 2^1 as a factor
    • Both have at least 3^1 as a factor
  3. Multiply the common prime factors together:
    • HCF(18, 24) = 2^1 \times 3^1 = 2 \times 3 = 6

Answer: 6

Example: Find the HCF of 36, 60 and 84.

  1. Find the prime factor decomposition of each number:
    • 36 = 2 \times 2 \times 3 \times 3 = 2^2 \times 3^2
    • 60 = 2 \times 2 \times 3 \times 5 = 2^2 \times 3^1 \times 5^1
    • 84 = 2 \times 2 \times 3 \times 7 = 2^2 \times 3^1 \times 7^1
  2. Find the common prime factors:
    • All have at least 2^2 as a factor
    • All have at least 3^1 as a factor
  3. Multiply the common prime factors together:
    • HCF(36, 60, 84) = 2^2 \times 3^1 = 4 \times 3 = 12

Answer: 12

Uses of the highest common factor

We can use the HCF to: