# Highest Common Factor

Go back to  'Arithmetic-Integers'

We know that the highest common factor (abbreviated as HCF) of two natural numbers x and y is the largest possible number which divides both x and y. For example, the HCF of

• 60 and 40 is 20, that is, HCF(60,40) = 20

• 100 and 150 is 50, that is, HCF(100,150) = 50

• 144 and 24 is 24, that is, HCF(144,24) = 24

• 17 and 89 is 1, that is, HCF(17,89) = 1

How can we find the HCF of two numbers? As an example, consider 120 and 144. Let us prime factorize each number:

$\begin{array}{l}120 = {2^3} \times {3^1} \times {5^1}\\144 = {2^4} \times {3^2}\end{array}$

Based on these, can you figure out what the HCF should be? Well, since the HCF is the highest common factor, we have to look for common prime factors of the two numbers. For example, 2 is a common prime factor of both numbers, so it will be a factor of the HCF as well. But how many factors of 2 will be in the HCF? Note that 120 has three factors of 2, while 144 has four factors of 2. Obviously, the number of factors of 2 in the HCF must be the smaller of the two, because the HCF must be a factor of both numbers. Thus, the number of factors of 2 in the HCF will be three. Similarly, the number of factors of 3 in the HCF will be one. Finally, there will be no factor of 5 in the HCF, since 5 is not a factor of the second number (144).

We conclude that the HCF is:

\begin{align}&{\rm{HCF}}\left( {120,\;144} \right) = {2^3} \times {3^1}\\&\qquad \qquad \qquad \quad= 24\end{align}

Let us take another example. What is the HCF of 600 and 3920? The prime factorizations of the two numbers will be as follows (verify this):

\begin{align}&\;\;600 = {2^3} \times {3^2} \times {5^1}\\&3920 = {2^4} \times {5^1} \times {7^2}\end{align}

As we discussed above, the HCF will be the product of the smallest power of each common prime factor in the two numbers:

${\rm{HCF}}\left( {600,\;3920} \right) = {2^3} \times {5^1} = 40$

Note that the HCF contains every possible common factor of the two numbers. This means that if you divide each of the two numbers by their HCF, the resulting pair of numbers will have no common factors. For example:

\begin{align}&\frac{{600}}{{40}} = 15\\&\frac{{3920}}{{40}} = 98\end{align}

The resulting numbers, 15 and 98, have no common factors, since all the possible common factors of 600 and 3920 have been taken out into the HCF, which is 40.

Learn math from the experts and clarify doubts instantly

• Instant doubt clearing (live one on one)
• Learn from India’s best math teachers
• Completely personalized curriculum