Highest Common Factor

Highest Common Factor

We have learnt in class VI that iteration is a process wherein a set of instructions or structures are repeated in a sequence for a specified number of times or until a condition is met. Here, we are going to learn to find HCF by listing all factors and find the biggest, then to find HCF by repeated subtraction and see to how much faster the iteration goes (and how in fewer steps you get the HCF) and then how to improve further by repeated division and remainder and that both lead to the same solution but one is faster than the other.

We know that, HCF is used in simplifying or reducing fractions. To understand how this concept applies in real life, imagine the following situation.

1. Methods to find HCF (Highest Common Factor):

1. Factorisation Method:

Situation:

Let us assume that you have 20 mangoes and 15 apples. You want to donate them together equally among the orphan children.

How many orphan children can you help at the maximum?

Here, basically question demands finding HCF of two numbers. HCF is Highest Common Factor, also known as GCD (Greatest Common Divisor). HCF of two or more than two numbers is such that, it is the largest possible number which divides given numbers completely.

Here, let us find the HCF of 20 mangoes and 15 apples.

Factors of 20 = 1,2,4, 5 ,10,20

Factors of 15 = 1,3, 5 ,15

So, the HCF of 20 and 15 is 5. That is, you can a help maximum of 5 orphan children.

So that for 5 children you can give 4 mangoes (20 ÷ 5 = 4)  and 3 apples (15 ÷ 5 = 3)  to each of them. In this way you can distribute equally the mangoes and the apples to each child.

2. Prime Factorisation Method:

Situation:

Suppose there are 18 students in Class VII and 27 in Class VIII and each class is divided into teams to prepare for an upcoming sports tournament, with the winning teams from each class play each other in the final. What would be the biggest possible team size that you could divide both these classes such that each team has exactly the same number of students and that no one is left behind.

The problem here is to find the HCF of 18 and 27.

Prime Factors of 18 = 2 x 3 x 3 

Prime Factors of 27 = 3 x 3 x 3 

Common prime factors of 18 and 27 = 3 x 3 = 9

So, the HCF of 18 and 27 is 9.

Now, let us learn some more methods of finding the HCF. The largest team member each group is 9, Std VII has 2 teams and Std VIII has 3 teams.

3. Repeated Division Method:

The above methods are easy to finding HCF, but for larger numbers these methods are tedious to find factors of the given numbers. In that case, alternatively we have some more methods to find HCF. Let us learn more about the other methods of finding the HCF.

For the above Situation, what if the Class VII had 396 students and Class VIII had 300 students? Then, what would be the biggest possible team size? Well, the above said two methods may not help us quickly. So, we can use continuous division method for finding the highest common factor.

STEP 1: Divide the larger number by the smaller number.

Here, 360 is the larger number. So, we divide 360 (Dividend) by 300 (Divisor). We get the Remainder as 96.

STEP 2: The remainder from Step 1 becomes the new divisor, and divisor of Step 1 becomes the new dividend.

From the step 1, we got 96 as remainder. So, in the second step 96 becomes the new divisor and 300 becomes the new dividend.

STEP 3: Repeat this division process till remainder becomes zero. The divisor of the last division (when remainder is zero) is the HCF.

From step 2, we got 12 as the new remainder which will become the new divisor. In the third step 12 becomes the new divisor and 96 becomes the new dividend. Now, the remainder is zero when 12 is the last divisor of the division. Therefore,12 is the required HCF.

Hence, the HCF of 396 and 300 is 12. So each team would be 12 students.

4. Repeated Subtraction Method:

To find the HCF for the given two numbers say m and n we do the subtraction continuously until m and n are equal. For example,

Find the HCF of 144 and 120

STEP 1: Check whether m = n

Here, take m = 144 and n = 120

Check whether m = n or m > n or m < n Here m > n (144 > 120).

STEP 2: m > n perform m – n repeat the process till m = n or m < n perform n – m repeat the process till m = n

If m is greater than n, then we perform m – n and assign the result (the difference) as m. Again we check whether m and n are equal or not and repeat the process. If m is less than n, then we perform n – m and we assign the result (the difference) as n. Again we check whether m and n are equal or not and the process is repeated.

Subtract 120(n) from 144(m) till m = n.

First 144 – 120 = 24 Repeat 120 – 24 = 96 Repeat 96 – 24 = 72

Repeat 72– 24=48 Repeat 48–24 = 24 Repeat 24 – 24 = 0

STEP 3: When m and n values are equal then that equal value will be the HCF (m, n).

Now m = n, Hence, we conclude that the HCF of 144 and 120 is 24.

Comparing both the repeated division and repeated subtraction methods, in finding the HCF, we can conclude that the repeated subtraction, in one way is easier and gives the HCF faster that the repeated division and also that one would want to easily do subtraction rather than division. Isn’t it ?