Highest Common Factor (HCF): The Division Method #
The Highest Common Factor (HCF), also known as the Greatest Common Divisor (GCD), is the largest positive integer that divides two or more numbers without leaving a remainder. In this guide, we’ll focus on finding the HCF of two numbers using the Division Method, which is also known as the Euclidean Algorithm.
1. Understanding the HCF #
Before we dive into the Division Method, let’s understand what the HCF actually means.
What is the HCF? #
The Highest Common Factor (HCF) of two or more numbers is the largest positive integer that divides each of the numbers without leaving a remainder.
Simple Example #
To find the HCF of 12 and 18:
- Factors of 12: 1, 2, 3, 4, 6, 12
- Factors of 18: 1, 2, 3, 6, 9, 18
- Common factors: 1, 2, 3, 6
- Highest Common Factor: 6
So, HCF(12, 18) = 6
2. The Division Method (Euclidean Algorithm) #
The Division Method, also known as the Euclidean Algorithm, is an efficient way to find the HCF of two numbers, especially for larger numbers where listing all factors would be time-consuming.
How the Division Method Works #
The Division Method involves repeated division until we get a remainder of zero. The last non-zero remainder is the HCF.
Steps to Find HCF Using the Division Method #
- Divide the larger number by the smaller number
- If the remainder is 0, the smaller number is the HCF
- If the remainder is not 0, divide the smaller number by the remainder
- Continue this process until the remainder becomes 0
- The last non-zero remainder is the HCF
Example 1: Finding HCF of 48 and 18 #
Step 1: Divide 48 by 18
48 ÷ 18 = 2 remainder 12
Step 2: Divide 18 by 12
18 ÷ 12 = 1 remainder 6
Step 3: Divide 12 by 6
12 ÷ 6 = 2 remainder 0
Since the remainder is now 0, the last non-zero remainder is 6.
Therefore, HCF(48, 18) = 6
Example 2: Finding HCF of 105 and 45 #
Step 1: Divide 105 by 45
105 ÷ 45 = 2 remainder 15
Step 2: Divide 45 by 15
45 ÷ 15 = 3 remainder 0
Since the remainder is now 0, the last non-zero remainder is 15.
Therefore, HCF(105, 45) = 15
3. Detailed Example: Finding HCF of 196 and 42 #
Let’s work through a more complex example step-by-step.
We want to find the HCF of 196 and 42.
Step 1: Divide the larger number (196) by the smaller number (42)
196 ÷ 42 = 4 remainder 28
Step 2: Now divide the previous divisor (42) by the remainder (28)
42 ÷ 28 = 1 remainder 14
Step 3: Now divide the previous divisor (28) by the remainder (14)
28 ÷ 14 = 2 remainder 0
Since the remainder is now 0, the last non-zero remainder is 14.
Therefore, HCF(196, 42) = 14
Verification #
We can verify our answer by checking if 14 divides both 196 and 42 without a remainder:
- 196 ÷ 14 = 14 (no remainder)
- 42 ÷ 14 = 3 (no remainder)
Indeed, 14 is the highest common factor of 196 and 42.
4. Visual Representation #
Sometimes it helps to organize our division steps in a table format for clarity:
Example: Finding HCF of 84 and 30 #
| Division Step | Answer | Remainder |
|---|---|---|
| 84 ÷ 30 | 2 | 24 |
| 30 ÷ 24 | 1 | 6 |
| 24 ÷ 6 | 4 | 0 |
Since the remainder is now 0, the last non-zero remainder is 6.
Therefore, HCF(84, 30) = 6
5. Tips and Tricks #
Here are some helpful tips to keep in mind when using the Division Method:
- Always start with the larger number: Divide the larger number by the smaller number first.
- Check your work: The HCF should divide both original numbers without a remainder.
- If one number perfectly divides the other: If there’s no remainder in the first division, the smaller number is the HCF.
- Co-prime numbers: If the HCF is 1, the numbers are said to be co-prime or relatively prime.
- For multiple numbers: To find the HCF of more than two numbers, first find the HCF of any two numbers, then find the HCF of this result and the third number, and so on.
6. Practice Problems #
Try these examples on your own to practice the Division Method:
- Find the HCF of 56 and 98
- Find the HCF of 120 and 144
- Find the HCF of 225 and 75
- Find the HCF of 84 and 90
Solutions:
1. HCF of 56 and 98
98 ÷ 56 = 1 remainder 42
56 ÷ 42 = 1 remainder 14
42 ÷ 14 = 3 remainder 0
Therefore, HCF(56, 98) = 14
2. HCF of 120 and 144
144 ÷ 120 = 1 remainder 24
120 ÷ 24 = 5 remainder 0
Therefore, HCF(120, 144) = 24
3. HCF of 225 and 75
225 ÷ 75 = 3 remainder 0
Therefore, HCF(225, 75) = 75
4. HCF of 84 and 90
90 ÷ 84 = 1 remainder 6
84 ÷ 6 = 14 remainder 0
Therefore, HCF(84, 90) = 6
