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 ?
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.