Highest Common Factor

There are 3 methods to calculate the HCF of two numbers,  

1. by listing out the factors
2. by prime factorization
3. division method

1. By listing out the common multiples

HCF of 30 and 42 

Step 1 - List out the factors of each number, 

Factors of 30 - 1, 2, 3, 5, 6, 10, 15, 30 

Factors of  42 - 1, 2, 3, 6, 7, 14, 21, 42

Step 2 - Circle all the common factors

Step 3 - 6 is the common factor and the greatest one.

Hence the HCF of 30 and 42 is 6.

2.  By prime factorization 

HCF of 60 and 90 

Step 1 - Represent the numbers in the prime factored form

 

HCF of 60 and 90 

Step 1 - Represent the numbers in the prime factored form

60 = 2 x 2 x 3 x 5 

90 = 2 x 3 x 3 x 5 

Step 2 - HCF is the product of the factors that are common. 

HCF of 60 and 90 = 2 x 3 x 5 = 30

 

Here is another example:

Find the HCF of 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 wait, 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 will be the product of the smallest power of each common prime factor:

\[\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: 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.

3. By common division method

HCF of 24 & 60 

Step 1 - Find a prime number which is a factor of both numbers. Write this prime number on the left of the two numbers, as shown

Step 2 -  Divide both numbers by this prime number, and write the quotients below the numbers.

Step 3 - Keep repeating both steps for the quotient obtained.

Step 4 - If you’re unable to find a common prime factor, then the HCF will be the product of all the numbers in the left column. 

Therefore the HCF of 24 and 60 is 2 x 2 x 3 = 12

Here is how Cuemath students learn to visualise HCF

Experience this in a Cuemath class. Book a Cuemath demo class with a nearby centre. 

Example 1: Find the HCF of 980 and 9000.

Solution: First, we carry out the prime factorization of the two numbers:

\[\begin{array}{*{20}{l}}2 \vert {980}\\\hline2 \vert {490}\\\hline5 \vert {245}\\\hline7 \vert {49}\\\hline7 \vert 7\\\hline{\;\;} \vert 1\end{array}   \begin{array}{*{20}{l}}2 \vert {9000}\\\hline2 \vert {4500}\\\hline2 \vert {2250}\\\hline3 \vert {1125}\\\hline3 \vert {375}\\\hline5 \vert {125}\\\hline5 \vert {25}\\\hline5 \vert 5\\\hline{\;\;} \vert 1\end{array}\]

Thus:

\[\begin{align}&\;\;980 = {2^2} \times {5^1} \times {7^2}\\&9000 = {2^3} \times {3^2} \times {5^3}\end{align}\]

We know that the HCF of these numbers will be the product of the smallest power of each common prime factor in the numbers:

\[ \Rightarrow \boxed{{\text{HCF}}\left( {980,\;9000} \right)\; = {2^2} \times {5^1} = 20}\]

Example 2: Here is another similar example. Find the HCF of 371250 and 29040.

Solution: Once again, we carry out the prime factorization of the two numbers:

\[\begin{array}{*{20}{l}}\;\;2\;\;\vert \;\;{371250}\\\hline\;\;3\;\;\vert \;\;{185625}\\\hline\;\;3\;\;\vert \;\;{61875}\\\hline\;\;3\;\;\vert \;\;{20625}\\\hline\;\;5\;\;\vert\;\; {6875}\\\hline\;\;5\;\;\vert \;\;{1375}\\\hline\;\;5\;\;\vert \;\;{275}\\\hline\;\;5\;\;\vert\;\; {55}\\\hline\;\;{11}\vert {11}\\\hline\;\;{\;\;\;\,}\vert \;\;1\end{array}         \begin{array}{*{20}{l}}\;\;2\;\;\vert \;\;{29040}\\\hline\;\;2\;\;\vert\;\; {14520}\\\hline\;\;2\;\;\vert {7260}\\\hline\;\;2\;\;\vert \;\;{3630}\\\hline\;\;3\;\;\vert \;\;{1815}\\\hline\;\;5\;\;\vert {605}\\\hline{11}\;\;\vert \;\;{121}\\\hline\;\;{11}\vert {11}\\\hline{\;\;\;\;\;\,}\vert \;\;\;1\end{array}\]

Thus:   \[\begin{align}&371250 = {2^1} \times {3^3} \times {5^4} \times {11^1}\\&\;\,29040 = {2^4} \times {3^1} \times {5^1} \times {11^2}\end{align}\]

Now, we can calculate the HCF and LCM:

\[\begin{align}
  {\text{HCF}}\left( {371250,\;29040} \right) &= {2^1} \times {3^1} \times {5^1} \times {11^1} \hfill \\
  \qquad \qquad \qquad \qquad \quad \; &= \boxed{330} \hfill 
\end{align} \]

Example 3: Find the HCF of the three numbers 168, 252 and 288.

Solution: We prime factorize the three numbers first. Verify that we will obtain the following:

\[\begin{align}&168 = {2^3} \times {3^1} \times {7^1}\\&252 = {2^2} \times {3^2} \times {7^1}\\&288 = {2^5} \times {3^2}\end{align}\]

The HCF of these numbers will be the product of the smallest power of each common prime factor in the numbers:

\[\begin{align}
  {\text{HCF}}\left( {168,\;252,\;288} \right) &= {2^2} \times {3^1} \hfill \\
  \qquad \qquad \qquad \qquad \quad  &= \boxed{12} \hfill \\ 
\end{align} \]

Challenge 1: Find the HCF of 6, 72 and 120, using the prime factorization method.

Challenge 2: Two positive numbers \(a\) and \(b\) are written as \(a = {x^3}{y^2}\) & \(b = x{y^3}\) ; \(x\) and \(y\) are prime numbers. Find \({\text{HCF}}(a,b)\).

⚡Tip:  The HCF of two numbers will be the product of the smallest power of each common prime factor in the two numbers.

Recall that IN "Finding HCF" section, we divide each of a pair of numbers by their HCF, the resulting numbers have no factors in common, since all the common factors have been taken out in the HCF.

Let \(x\) and \(y\) be the two numbers. Now, consider the following relations:

\[\begin{gathered}
  x = {\text{HCF(}}x,y{\text{)}} \times a \hfill \\
  y = {\text{HCF(}}x,y{\text{)}} \times b \hfill \\ 
\end{gathered} \]

Here, \(a\) and \(b\) are some positive integers. Also, we have written each of \(x\) and \(y\) as a product of their HCF and another number. Clearly, \(a\) and \(b\) will have no factors in common.

Now, think about the LCM of \(x\) and \(y\). It should be a multiple of both x and y. Obviously, it should have the HCF as a factor, but it should also have \(a\) and \(b\) as factors. That is, the LCM should be divisible by: the HCF, \(a\) and \(b\). Only then can it be a multiple of both \(x\) and \(y\). A little more thinking will show that the LCM will be:

\[{\rm{LCM}} = {\rm{HCF}} \times a \times b\]

This product is the lowest possible number which will be a common multiple of both \(x\) and \(y\), and so it is the LCM. Convince yourself about this. If you have difficulty understanding this, work with a couple of concrete examples.

Now, According to above results,

\[\begin{align}x\times y &= \left( {{\rm{HCF}} \times a} \right) \times \left( {{\rm{HCF}} \times b} \right)\\\qquad&= {\rm{HCF}} \times \left( {{\rm{HCF}} \times a \times b} \right)\\\qquad &= {\rm{HCF}} \times {\rm{LCM}}\end{align}\]

\[ \Rightarrow \boxed{x \times y = {\text{HCF}} \times {\text{LCM}}}\]

Thus, the product of the HCF and LCM of two numbers \(x\) and \(y\) is the product of \(x\) and \(y\). 

✍Note: if we have the HCF of two numbers, we can evaluate the LCM directly, and vice-versa:

\[\begin{align}{\rm{LCM}}\left( {x,\;y} \right) &= \frac{{x \times y}}{{{\rm{HCF}}\left( {x,\;y} \right)}}\\{\rm{HCF}}\left( {x,y} \right) &= \frac{{x \times y}}{{{\rm{LCM}}\left( {x,y} \right)}}\end{align}\]

Challenge 3: Consider the numbers 24 and 60. Their HCF is 12. Find LCM.

Challenge 4: Given that HCF (306, 657) = 9, find LCM (306, 657)

⚡Tip: Use relation between HCF and LCM.

• The listing method works best for the smaller numbers.
  For example, listing factors of 15 & 20 and finding out the highest common factor is easier.
• With larger numbers listing factors would be a tedious task. It is best to use the prime factorization method.
  For example, listing factors for 150 and 242 would be very tedious. Prime factorization of these numbers would be simpler.
• When you have to find out the HCF of 3 or more numbers using the common division method would be the best. It gives the flexibility to factorize the numbers simultaneously.

• Misconception: One is the HCF of any two numbers
  The highest common factor is the greatest common factor of the two numbers. Well, 1 can be the HCF when two numbers don’t have any common factors other than one. However, when numbers have more than one common factor the greatest number would be the HCF.

1. Find HCF of 25 and 63
   __________________________
    
2. Find HCF of 24 and 60 
   __________________________
    
3. Find HCF of 99 & 96
   __________________________
    
4. Find HCF of 44, 64, 96
   __________________________
    
5. Find HCF of 480 and 720?
   __________________________