Now that we are well acquainted with the concept of Factors, it is time to move on. If you haven't read that explanation, take a look! Previously, we learned how to find the Common Factors between two (or more) numbers. At the end of the topic, we stated that recognising these common factors can help us determine the highest common factor shared between these given numbers.
The highest common factor is a helpful tool that can be used to reduce fractions and ratios. It is also used to simplify expressions and equations so that it is easier for us to solve. Throughout this topic, we shall abbreviate the highest common factor by HCF.
Highest Common Factor Meaning
We can think of the HCF as the greatest number that is divisible by a set of given numbers. In other words, let \(x\) and \(y\) be two whole numbers. The HCF of \(x\) and \(y\) is the largest possible number that divides both \(x\) and \(y\) completely without leaving a remainder. With this in mind, we can describe the HCF with the following definition.
Recall that a common factor is a number that divides a pair of whole numbers precisely resulting in a remainder equal to zero.
The highest common factor (HCF) is the largest common factor of two (or more) whole numbers.
Let us denote the HCF by the letter \(a\). We can write the HCF of \(x\) and \(y\) by the following notation,
\[ \mbox{HCF}(x,y) = a.\]
In some textbooks, the HCF can also be referred to as the greatest common factor (GCF) or the greatest common divisor (GCD). Let us demonstrate this with an example.
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.
Highest common factor of prime numbers
Prime Numbers are numbers that are only divisible by 1 and themselves. This means that a prime number has only two factors, that is, 1 and itself. So, what if we had to find the HCF of two prime numbers? Here's an example.
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.
This example leads us to the following result: the HCF of two (or more) prime numbers is always equal to 1. This statement is true for all given sets of prime numbers.
Why not give it a go? Try finding the HCF between the prime numbers 3, 17, and 29. You'll see that the result is also 1!
Characteristics of highest common factor
The HCFs of two (or more) numbers have several notable properties we should familiarise ourselves with. These are listed below.
The HCF of two (or more) numbers divides each given number without leaving a remainder.
The HCF of two (or more) numbers is a factor of each given number.
The HCF of two (or more) numbers is always less than or equal to each given number.
The HCF of two (or more) prime numbers is always 1.
In the next section, we shall move on to the different techniques for finding the HCF of two (or more) numbers.
Methods for Finding the highest common factor
There are three ways to find the HCF of two (or more) numbers.
- Listing factors method.
- Prime factorisation.
- Division method.
Here, we hope to learn how to apply each method and introduce several worked examples showing each approach.
Highest Common Factor: Listing factors method
The listing factors method is the most straightforward technique when finding the HCF. The example seen in the previous section uses this method. There are three steps to this method.
List the factors of each given number.
Find the common factors between these numbers.
Determine the highest common factor among this list of common factors. This number is the HCF.
Let us look at some worked examples.
Highest common factor of two numbers with the listing factors method
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\).
Highest common factor of three numbers with the listing factors method
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.\)
Highest common factor of four numbers with the listing factors method
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.\)
Although this method is very straightforward and can be used to find the HCF of two or numbers, it can be rather tricky especially when dealing with bigger numbers. This is where the other two ways of finding the HCF come in!
Highest Common Factor: Prime factorisation method
Prime factorisation is a process used to represent a number as a product of its prime factors. A more detailed discussion of this topic can be found in the article: Prime Factorisation. There are three steps to finding the HCF of two (or more) numbers using this method.
Express the given numbers in their prime factored form.
Find the common prime factors of the given numbers.
Multiply the common prime factors. This product is the HCF of the given numbers.
To view this clearly, let us demonstrate this with the following examples.
Highest common factor of two numbers with the prime factorisation method
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.\)
Highest common factor of three numbers with the prime factorisation method
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.\)
Highest common factor of four numbers with the prime factorisation method
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.\)
Highest Common Factor: Division method
For this approach, we shall make use of long division. Below are the steps to this method.
Using long division, divide the larger number by the smaller number.
If the remainder is equal to 0, then the divisor is the HCF.
If the remainder is not equal to 0, then we shall make the remainder of Step 1 the divisor and the divisor from Step 1 the dividend. In doing so, conduct long division again.
If the remainder is equal to 0, then the divisor of the last division is the HCF.
If the remainder is not equal to 0, then repeat Step 3 until the remainder equals 0.
Division method for multiple numbers
We need to tweak the division method when it comes to finding the HCF of more than two numbers. Here, we need to group the numbers into equal groups (of two) and perform long division as before. In doing so, we are essentially breaking down the division involved into a string of steps that are less complicated.
Determine the HCF of the first two of the given numbers via the division method above.
Find the HCF of the third number and the HCF found from the first two numbers in Step 1.
This gives the HCF of the three numbers.
Repeat Step 2 to find the HCF of the fourth number and the HCF found from the first three numbers in Step 3.
This gives the HCF of the four numbers.
Let us now look at some worked examples.
Highest common factor of two numbers with the division method
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.\)
Highest common factor of three numbers with the division method
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}\]
As the remainder in Step 2 is equal to 0, the divisor = 11 is the HCF of all three given numbers. Thus, \( \mbox{HCF}(33, 121, 154) = 11.\)
Highest common factor of four numbers with the division method
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.\)
Highest common factor vs lowest common multiple
The lowest common multiple (LCM) is the smallest common multiple for a given set of numbers. You can find more information on this topic in the article: Lowest Common Multiple. In this section, we shall make comparisons between the HCF and LCM. This contrast is seen in the table below.
The table below compares the HCF and LCM of two whole numbers, x and y.
Highest Common Factor (HCF) | Lowest Common Multiple (LCM) |
The GCF of two whole numbers \(x\) and \(y\) is the greatest number that divides both\(x\) and \(y\) completely. | The LCM of two whole numbers \(x\) and \(y\) is the smallest number which is a multiple of both \(x\) and \(y\) . |
The intersection between the set of common factors of \(x\) and \(y\) is the greatest value. | The intersection between the set of common multiples of \(x\) and \(y\) is the minimum value. |
Denoted by \(\mbox{GCF}(x, y) = a\), where \(a\) is the GCF of \(x\) and \(y\) | Denoted by \(\mbox{LCM}(x, y) = b\), where \(b\) is the LCM of \(x\) and \(y\) |
Relationship between highest common factor and lowest common multiple
Despite their differences, the HCF and LCM of two numbers happen to have a clever link to one another. Let's say we have two whole numbers, \(x\) and \(y\). The HCF and LCM of these two numbers are denoted by \( \mbox{HCF}(x, y) \) and \( \mbox{LCM}(x, y)\). These two concepts are related by the following notion: the product of the HCF and LCM of \(x\) and \(y\) is equal to the product of \(x\) and \(y\). We can write this as the notation below,
\[ \mbox{HCF}(x,y) \cdot \mbox{LCM}(x,y) = xy.\]
Here is an example that demonstrates this.
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.
This formula is true for all given sets of numbers. Try it out with the examples given throughout this discussion.
We shall end our discussion with a final example of finding the HCF of a pair of numbers using all three methods studied above.
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.\)
Highest Common Factor - Key takeaways
- The HCF is the largest common factor of two whole numbers and is denoted by HCF(x, y) = a.
- The HCF of two numbers divides each given number without leaving a remainder.
- The HCF of two numbers is a factor of each given number.
- The HCF of two numbers is always less than or equal to each given number.
- The HCF of two (or more) prime numbers is always 1.
- Listing method for finding HCF.
List the factors of each number.
Find the common factors between these numbers.
Determine the highest common factor among this list of common factors.
Prime factorisation method for finding HCF.
Express the numbers in their prime factored form.
Find the common prime factors of these numbers.
Multiply the common prime factors.
Division method for finding HCF.
Divide the larger number by the smaller number via long division.
If the remainder is 0, then the divisor is the HCF.
If the remainder is not 0, then from Step 1, make the remainder the divisor and the divisor the dividend. Perform long division once more.
If the remainder is 0, then the divisor of the last division is the HCF.
If the remainder is not 0, then repeat Step 3 until the remainder equals 0.
Relationship between HCF and LCM:
\[ \mbox{HCF}(x,y) \cdot \mbox{LCM}(x,y) = xy.\]
Explanations 
Textbooks 
Exams 
Magazine 
