HCF Using Prime Factors

Welcome back to Finding the Highest Common Factor! You are now on Lesson 3 of 4 in this course, which means you have already built a solid foundation. In the first two lessons, we identified common factors by listing and comparing factor lists, then selected the greatest one to find the HCF. That approach is reliable, but it can get slow when numbers grow larger.

In this lesson, we will learn a more efficient route: finding the HCF directly from the prime factorizations of the numbers involved. If you completed the earlier course on breaking numbers into primes, those skills are about to pay off in a big way.

Listing every factor of a number works well for small values like $12$ or $18$. But imagine finding all the factors of $252$ or $360$ — the lists get long, and mistakes become easy to make.

Prime factorization gives us a shortcut because it breaks each number down to its basic building blocks. As you may recall from a previous course, every whole number greater than $1$ has a unique prime factorization. Comparing those building blocks tells us exactly what two numbers have in common, without writing out every single factor. The core idea is simple: if a prime appears in both factorizations, it contributes to the HCF; if it appears in only one, it does not.

Here is the step-by-step process for finding the HCF using prime factorization:

1. Find the prime factorization of each number.
2. Identify the primes that appear in every factorization (the shared primes).
3. For each shared prime, take the lowest power that appears across the factorizations.
4. Multiply these together to get the HCF.

If no prime is shared at all, the HCF is simply $1$. As we saw in the previous lesson, that just means the numbers are coprime.

Let's see the method in action. First, we write the prime factorizations:

Now we compare prime by prime:

Both factorizations contain $2$ and $3$, so both primes are shared. We take $2$ at its lowest power ($2^2$) and $3$ at its lowest power ($3^1$), then multiply:

You can verify this with factor lists if you like: the factors common to $36$ and $48$ are $1, 2, 3, 4, 6, 12$, and the greatest is indeed $12$.

You might wonder why we ignore a prime that appears in only one factorization. The reason comes straight from the definition of "factor." For a number to divide both values evenly, every prime in that number must be present in both factorizations. A prime that is missing from one side simply cannot be part of any common factor.

Let's explore this with $60$ and $90$:

Here, the primes $2$, $3$, and $5$ all appear in both factorizations, so each one contributes. Taking the lowest powers:

It is also worth understanding why we pick the lowest power of each shared prime, not the highest. Look at the prime $2$ in the example above: it appears as $2^2$ in $60$ and as $2^1$ in $90$. If we tried to include $2^2$ in the HCF, the result would contain a factor of $4$. But $90$ is not divisible by $4$, so a number containing $2^2$ could not divide $90$ evenly.

By choosing the lower power, we guarantee the HCF divides both numbers without a remainder. The lowest power is the most that both numbers can "afford" to share.

The method works the same way with three or more numbers. A prime must appear in all factorizations to be included, and we still take the lowest power across the entire set. Let's find the HCF of $24$, $36$, and $60$:

The prime $5$ appears only in the factorization of $60$, so it is excluded. Multiplying the shared primes at their lowest powers gives us:

Notice that adding a third number to the set kept the HCF the same or made it smaller compared to any pair, because each new factorization adds another filter.

For small numbers, listing factors and comparing them is perfectly fine. The prime factorization method shows its true strength with larger numbers, where full factor lists would be long and error-prone. Consider finding the HCF of $168$ and $252$:

The shared primes are $2$, $3$, and $7$, taken at powers $2$, $1$, and $1$ respectively:

We reached the answer in just a few lines — no need to list over a dozen factors for each number. Think about a scenario where a warehouse has 168 bottles of water and 252 bottles of juice and needs to pack them into the largest possible number of identical supply kits with no leftovers. The HCF tells us that $84$ kits can be made, each containing $2$ waters and $3$ juices. The bigger the numbers, the more time this method saves.

In this lesson, we learned how to find the HCF by comparing prime factorizations rather than full factor lists. The process comes down to three ideas: identify the primes shared by all numbers, take each shared prime at its lowest appearing power, and multiply. We also explored why primes found in only one factorization are left out and why higher powers of shared primes cannot be used, since including them would produce a number that no longer divides every value in the set.

Now it is time to put this method into practice! The upcoming exercises will walk you through guided fill-in-the-blank examples first, then challenge you with larger numbers and sets of three, so you can build real confidence with this powerful technique.