Highest Common Factor

What is the HCF of 14 and 21?

Solution

Let us first list down the factors of 14. The number 14 can be written as the product of the following pairs of numbers.

\[ \begin{align} 1 \cdot 14 &= 14 \\ 2 \cdot 7 &= 14. \end{align} \]

Thus, the factors of 14 are 1, 2, 7, and 14. Next, let us list down the factors of 21. Applying the same method as before, we have

\[ \begin{align} 1 \cdot 21 &= 21 \\ 3 \cdot 7 &= 21. \end{align} \]

Thus, the factors of 21 are 1, 3, 7, and 21. Listing these two lists of factors and comparing them, we find that the common factors of 14 and 21 are 1 and 7. Between these two common factors, observe that 1 is less than 7.

Therefore, 7 is the highest common factor between 14 and 21. Indeed, 7 divides both 14 and 21.

Find the HCF of 23 and 31.

Solution

The numbers 23 and 31 are indeed prime as they are not divisible by any other number apart from 1 and itself. Thus, their factors are simply listed below.

Factors of 23: 1 and 23

Factors of 31: 1 and 31

Observe that the only common factor between these two numbers is 1. As there are no other common factors to compare this to, we conclude that the HCF of 23 and 31 is 1.

Find the HCF of 27 and 36.

Solution

Step 1: Let us list the factors of 27 and 36.

Factors of 27: 1, 3, 9, 27

Factors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36

Step 2: From these two lists, let us determine the common factors shared between 27 and 36.

Common factors of 27 and 36: 1, 3, 9.

Step 3: Finally, we shall identify the largest common factor in this list.

Here, 9 is the largest common factor. Thus, \( \mbox{HCF}(27,36) = 9\).

Find the HCF of 7, 35, and 42.

Solution

Step 1: Let us list the factors of 7, 35, and 42.

Factors of 7: 1, 7

Factors of 35: 1, 5, 7, 35

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

Step 2: From these three lists, let us determine the common factors shared between 7, 35, and 42.

Common factors of 7, 35, and 42: 1 and 7.

Step 3: Finally, we shall identify the largest common factor in this list.

Here, 7 is the largest common factor. Thus, \(\mbox{HCF}(7, 35, 42) = 7.\)

Find the HCF of 12, 15, 21, and 24.

Solution

Step 1: Let us list the factors of 12, 15, 21, and 24.

Factors of 12: 1, 2, 3, 4, 6, 12

Factors of 15: 1, 3, 5, 15

Factors of 21: 1, 3, 7, 21

Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24

Step 2: From these three lists, let us determine the common factors shared between 12, 15, 21, and 24.

Common factors of 12, 15, 21, and 24: 1 and 3.

Step 3: Finally, we shall identify the largest common factor in this list.

Here, 3 is the largest common factor. Thus, \(\mbox{HCF}(12, 15, 21, 24) = 3.\)

Find the HCF of 24 and 32.

Solution

Step 1: We shall write each number as a product of primes.

Prime factorization of 24:

\[ \begin{array}{c|c} 2 & 24 \\ \hline 2 & 12 \\ \hline 2 & 6 \\ \hline 3 & 3 \\ \hline & 1 \end{array} \]

\[24 = 2\cdot 2\cdot 2\cdot 3 = 2^3 \cdot 3\]

Prime factorization of 32:

\[ \begin{array}{c|c} 2 & 32 \\ \hline 2 & 16 \\ \hline 2 & 8 \\ \hline 2 & 4 \\ \hline 2& 2 \\ \hline & 1 \end{array} \]

\[32 = 2\cdot 2\cdot 2\cdot 2 \cdot 2 = 2^5\]

Step 2: List the common primes of 24 and 32.

\[\begin{align} 24 &= 2\cdot 2\cdot 2\cdot 3 \\ 32 &= 2\cdot 2\cdot 2\cdot 2 \cdot 2 .\end{align} \]

Here, the common primes of 24 and 32 are the three instances of the number 2.

Step 3: Multiply the common factors.

\[ 2\cdot 2\cdot 2=8.\]

Thus, \(\mbox{HCF}(24, 32) = 8.\)

Find the HCF of 8, 12, and 20.

Solution

Step 1: We shall write each number as a product of primes.

Prime factorization of 8:

\[ \begin{array}{c|c} 2 & 8 \\ \hline 2 & 4 \\ \hline 2 & 2 \\ \hline & 1 \end{array} \]

\[8 = 2\cdot 2\cdot 2\cdot = 2^3 \]

Prime factorization of 12:

\[ \begin{array}{c|c} 2 & 12 \\ \hline 2 & 6 \\ \hline 3 & 3 \\ \hline & 1 \end{array} \]

\[12 = 2\cdot 2\cdot 3 = 2^2 \cdot 3\]

Prime factorization of 20:

\[ \begin{array}{c|c} 2 & 20 \\ \hline 2 & 10 \\ \hline 5 & 5 \\ \hline & 1 \end{array} \]

\[20 = 2\cdot 2\cdot 5 = 2^2 \cdot 5\]

Step 2: List the common primes of 8, 12 and 20.

\[\begin{align} 8 &= 2\cdot 2\cdot 2\cdot \\ 12 &= 2\cdot 2\cdot 3 \\ 20 &= 2\cdot 2\cdot 5 .\end{align} \]

Here, the common primes of 8, 12, and 20 are the two instances of the number 2.

Step 3: Multiply the common factors.

\[2 \cdot 2 = 4.\]

Thus, \( \mbox{HCF}(8, 12, 20) = 4.\)

Find the HCF of 9, 27, 36, and 45.

Solution

Step 1: We shall write each number as a product of primes.

Prime factorization of 9:

\[ \begin{array}{c|c} 3 & 9 \\ \hline 3 & 3 \\ \hline & 1 \end{array} \]

\[9 = 3\cdot 3 = 3^2\]

Prime factorization of 27:

\[ \begin{array}{c|c} 3 & 27 \\ \hline 3 & 9 \\ \hline 3 & 3 \\ \hline & 1 \end{array} \]

\[27 = 3\cdot 3\cdot 3 = 3^3\]

Prime factorization of 36:

\[ \begin{array}{c|c} 2 & 36 \\ \hline 2 & 18 \\ \hline 3 & 9 \\ \hline 3 & 3 \\ \hline & 1 \end{array} \]

\[36 = 2\cdot 2\cdot 3\cdot 3 = 2^2 \cdot 3^2\]

Prime factorization of 45

\[ \begin{array}{c|c} 3 & 45 \\ \hline 3 & 15 \\ \hline 5 & 5 \\ \hline & 1 \end{array} \]

\[45 = 3\cdot 3\cdot 5 = 3^2 \cdot 5\]

Step 2: List the common primes of 9, 27, 36, and 45.

\[\begin{align} 9 &= 3\cdot 3 \\ 27 &= 3\cdot 3\cdot 3 \\ 36 &= 2\cdot 2\cdot 3\cdot 3 \\ 45 &= 3\cdot 3\cdot 5 .\end{align} \]

Here, the common primes of 9, 27, 36, and 45 are the two instances of the number 3.

Step 3: Multiply the common factors.

\[ 3 \cdot 3 = 9\]

Thus, \( \mbox{HCF}( 9, 27, 36, 45) = 9.\)

Find the HCF of 40 and 50.

Solution

Step 1: Divide 50 by 40.

\[ \begin{array}{rl} 1 & \\40\; \enclose{longdiv}{\;50} \kern-.2ex\\ \underline{40} \, & \\ 10 \, & \end{array}\]

Step 2: Since the remainder is not 0, make the remainder (= 10) the divisor and the divisor (= 40) the dividend.

\[ \begin{array}{rl} 4 & \\10\; \enclose{longdiv}{\;40} \kern-.2ex\\ \underline{40} \, & \\ 0 \, & \end{array}\]

Step 3: As the remainder in Step 2 is equal to 0, the divisor = 10 is the HCF.

Thus, \( \mbox{HCF}(40, 50) = 10.\)

Find the HCF of 33, 121, and 154.

Solution

Step 1(a): Find the HCF of 33 and 121 using long division.

\[ \begin{array}{rl} 3 & \\33\; \enclose{longdiv}{\;121} \kern-.2ex\\ \underline{99} \, & \\ 22 \, & \end{array}\]

Step 1(b): Since the remainder is not 0, make the remainder (= 22) the divisor and the divisor (= 33) the dividend.

\[ \begin{array}{rl} 1 & \\22\; \enclose{longdiv}{\;33} \kern-.2ex\\ \underline{22} \, & \\ 11 \, & \end{array}\]

Step 1(c): Since the remainder is not 0, make the remainder (= 11) the divisor and the divisor (= 22) the dividend.

\[ \begin{array}{rl} 1 & \\11\; \enclose{longdiv}{\;22} \kern-.2ex\\ \underline{22} \, & \\ 0\, & \end{array}\]

The remainder is finally equal to 0. Thus, the divisor = 11 is the HCF of 33 and 121.

Step 2: Now that we have the HCF of 33 and 121, let us now find the HCF of 33, 121, and 154. To do so, make the HCF (of 33 and 121) found in Step 1(c) the divisor and 154 the divided. Apply long division as usual.

\[ \begin{array}{rl} 14 & \\11\; \enclose{longdiv}{\;154} \kern-.2ex\\ \underline{154} \, & \\ 0 \, & \end{array}\]

Thus, \( \mbox{HCF}(33, 121, 154) = 11.\)

Find the HCF of 24, 48, 63, and 75.

Solution

Step 1: Find the HCF of 24 and 48 using long division.

\[ \begin{array}{rl} 2 & \\24\; \enclose{longdiv}{\;48} \kern-.2ex\\ \underline{48} \, & \\ 0 \, & \end{array}\]

As the remainder is equal to 0, the divisor = 24 is the HCF of 24 and 48.

Step 2(a): Now that we have the HCF of 24 and 48, let us now find the HCF of 24, 48, and 63. To do so, make the HCF (of 24 and 48) found in Step 1 the divisor and 63 the divided. Perform long division as before.

\[ \begin{array}{rl} 2 & \\24\; \enclose{longdiv}{\;63} \kern-.2ex\\ \underline{48} \, & \\ 15 \, & \end{array}\]

Step 2(b): Since the remainder is not 0, make the remainder (= 15) the divisor and the divisor (= 24) the dividend.

\[ \begin{array}{rl} 1 & \\15\; \enclose{longdiv}{\;24} \kern-.2ex\\ \underline{15} \, & \\ 9 \, & \end{array}\]

Step 2(c): Since the remainder is not 0, make the remainder (= 9) the divisor and the divisor (= 15) the dividend.

\[ \begin{array}{rl} 1 & \\9\; \enclose{longdiv}{\;15} \kern-.2ex\\ \underline{9} \, & \\ 6 \, & \end{array}\]

Step 2(d): Since the remainder is not 0, make the remainder (= 6) the divisor and the divisor (= 9) the dividend.

\[ \begin{array}{rl} 1 & \\6\; \enclose{longdiv}{\;9} \kern-.2ex\\ \underline{6} \, & \\ 3 \, & \end{array}\]

Step 2(e): Since the remainder is not 0, make the remainder (= 3) the divisor and the divisor (= 6) the dividend.

\[ \begin{array}{rl} 2 & \\3\; \enclose{longdiv}{\;6} \kern-.2ex\\ \underline{6} \, & \\ 0 \, & \end{array}\]

The remainder is finally equal to 0. Thus, the divisor = 3 is the HCF of 24, 48, and 63.

Step 3: As we now have the HCF of 24, 48, and 63, we finally need to find the HCF of 24, 48, 63, and 75. We do this by making the HCF (of 24, 48, and 63) found in Step 2(e) the divisor and 75 the divided. Apply long division as usual.

\[ \begin{array}{rl} 25 & \\3\; \enclose{longdiv}{\;75} \kern-.2ex\\ \underline{75} \, & \\ 0 \, & \end{array}\]

Here the remainder is equal to 0. So the divisor = 3 is the HCF of all four given numbers.

Thus, \( \mbox{HCF}(24, 48, 63, 75) = 3.\)

Verify that the above formula is satisfied for the numbers 9 and 12.

Solution

Let us first find the HCF of 9 and 12. Using the listing method, we obtain:

Factors of 9: 1, 3, 9

Factors of 12: 1, 2, 3, 4, 6, 12

Common factors of 9 and 12: 1 and 3

Thus, HCF(9, 12) = 3

Now, let us find the LCM of 9 and 12. To find the LCM, refer to the topic: Lowest Common Multiple.

\[ \begin{array}{c|c} 3 &9 \; 12 \\ \hline 2 & 3, \; 4 \\ \hline 2 & 3,\; 2 \\ \hline 3 & 3,\; 1 \\ \hline & 1,\;1 \end{array} \]

\[36 = 3\cdot 2\cdot 2\cdot 3\]

Thus \( \mbox{LCM}(9, 12) = 36.\)

Referring to the given formula, we first note that the product of 9 and 12 is equal to 108. Now, let us deduce the product of their HCF and LCM.

\[ \mbox{HCF}(9,12) \cdot \mbox{LCM}(9,12) = 3\cdot 36 = 108.\]

As you can see, the product of the HCF and LCM of 9 and 12 is also equal to the product of 9 and 12. Thus, the formula holds for this pair of numbers.

Determine the HCF of 45 and 72 using the listing method, prime factorisation method, and division method for finding the HCF.

Listing method

Step 1: Let us list the factors of 45 and 72.

Factors of 45: 1, 3, 5, 9, 15, 45

Factors of 72: 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72

Step 2: From these two lists, let us determine the common factors shared between 45 and 72.

Common factors of 45 and 72: 1, 3, 9

Step 3: Finally, we shall identify the largest common factor in this list.

Here, 9 is the largest common factor. Thus, \( \mbox{HCF}(45, 72) = 9.\)

Prime factorisation method

Step 1: We shall write each number as a product of primes.

Prime factorization of 45

\[ \begin{array}{c|c} 3 & 45 \\ \hline 3 & 15 \\ \hline 5 & 5 \\ \hline & 1 \end{array} \]

\[45 = 3\cdot 3\cdot 5 = 3^2 \cdot 5\]

Prime factorization of 72

\[ \begin{array}{c|c} 2 & 72 \\ \hline 2 & 36 \\ \hline 2 & 18 \\ \hline 3 & 9 \\ \hline 3 & 3 \\ \hline & 1 \end{array} \]

\[72 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 3\cdot 3 = 2^3 \cdot 3^2\]

Step 2: List the common primes of 45 and 72.

\[\begin{align} 45 &= 3\cdot 3\cdot 5 \\ 72 &= 2 \cdot 2 \cdot 2 \cdot 2 \cdot 3\cdot 3 .\end{align} \]

Here, the common primes of 45 and 72 are the two instances of the number 3.

Step 3: Multiply the common factors

\[ 3\cdot 3 = 9 \]

Thus, \( \mbox{HCF}(45, 72) = 9.\)

Division method

Step 1: Divide 72 by 45

\[ \begin{array}{rl} 1 & \\45\; \enclose{longdiv}{\;72} \kern-.2ex\\ \underline{45} \, & \\ 27 \, & \end{array}\]

Step 2: Since the remainder is not 0, make the remainder = 27 the divisor = 45 the dividend.

\[ \begin{array}{rl} 1 & \\27\; \enclose{longdiv}{\;45} \kern-.2ex\\ \underline{27} \, & \\ 18 \, & \end{array}\]

Step 3: Since the remainder is not 0, make the remainder = 18 the divisor = 27 the dividend.

\[ \begin{array}{rl} 1 & \\18\; \enclose{longdiv}{\;27} \kern-.2ex\\ \underline{18} \, & \\ 9 \, & \end{array}\]

Step 4: Since the remainder is not 0, make the remainder = 9 the divisor = 18 the dividend.

\[ \begin{array}{rl} 2 & \\9\; \enclose{longdiv}{\;18} \kern-.2ex\\ \underline{18} \, & \\ 0 \, & \end{array}\]

Step 5: As the remainder in Step 4 is equal to 0, the divisor = 9 is the HCF.

Thus, \( \mbox{HCF}(45, 72) = 9.\)