Contents
Highest Common Factor (H.C.F)
The Highest Common Factor (H.C.F) of two or more given numbers is the highest (or greatest ) of their common factors. It is also called as Greatest Common Divisor ( GCD ) or Greatest Common Mmeasure ( GCM )
In other words, the H.C.F. of two or more numbers is the largest number that divides all the given numbers exactly.
For example consider the numbers 24 and 36
|
Number |
24 |
36 |
|
Factors of the number |
1,2,3,4,6,8,12,24 |
1,2,3,4,6,9,12,36 |
Common factors of 24 and 36 are: 1,2,3,4,6,12
Out of these common factors we find that 12 is the greatest. Therefore, H.C.F. of 24 and 36 is 12.
Note: H.C.F. of two co-prime numbers is always 1.
There are two commonly used methods for finding H.C.F. of two or more numbers:
1)Prime Factorization Method
2)Continued Division Method
Prime Factorization Method
In order to find the H.C.F. of two or more numbers, we may follow the following procedure:
STEP 1) Obtain the numbers. Let the numbers be 90 and 48.
STEP 2) Write prime factorization of the given numbers.
We have,
90 = 2 x 3 x 3 x 5 and 48 = 2 x 2 x 2 x 2 x 3
STEP 3) Identify common prime factors.
In case of 90 and 48, common prime factors are 2 and 3
STEP 4) For each common prime factor find the minimum number of times it occurs in the prime factorizations of the given numbers.
For example, the prime factor 2 appears minimum number of 1 time in the prime factorization of 90 and the prime factor 3 appears minimum number of 1 time in the prime factorization of 48.
STEP 5) Multiply each common prime factor the number of times determined in STEP (4) and find their product to get the required H.C.F.
Therefore, H.C.F. of 90 and 48 is = 2 x 3 = 6
Following examples will illustrate the above method.
Example 1: Find the H.C.F. of 850 and 680 by prime factorization method.
Solution:
Example 2: Find the H.C.F. of 20, 28 and 36 by prime factorization method.
Solution:
Continued Division Method ( EUCLID’S ALGORITHM )
STEP 1) Obtain the two numbers and identify the greatest number.
STEP 2) Take the greatest number as dividend and the smaller one as divisor.
STEP 3) Find the quotient and remainder.
STEP 4) If the remainder is zero, then divisor is the required H.C.F. Otherwise, go to next step.
STEP 5) Take the remainder as the new divisor and the divisor as the new dividend.
STEP 6) Repeat steps (3), (4) and (5) till the remainder zero is obtained. The last divisor, for which the remainder is zero, is the required H.C.F.
Illustrative Example:
Find the HCF of 161 and 345 by the division method.
Solution: 
Hence, the HCF of 161 and 345 is 23.
H.C.F. of more than two numbers
STEP 1) Find the H.C.F. of any two of them.
STEP 2) Find the H.C.F. of the third number and H.C.F. obtained in STEP (1)
STEP 3) Take the H.C.F. obtained in STEP (2) as the required H.C.F. of three given numbers.
Illustrative Example:
Find the HCF of 136, 170 and 255.
Solution: 
H.C.F. of larger numbers
The prime factorization method for finding the H.C.F. of given numbers is convenient when the numbers are small. For larger numbers, we use a faster method. In this method, we follow the following steps:
STEP 1) Obtain the numbers
STEP 2) Obtain a common factor of the given numbers
STEP 3) Divide the numbers by the common factor obtained in STEP (2) and write the resultant quotients.
STEP 4) Obtain a common factor of the resultant quotients obtained in the STEP (3)
STEP 5) Repeat STEPS (3) and (4) until there are no common factors left
STEP 6) Find the product of all the common divisors obtained in the above steps. This product gives the H.C.F. of the given numbers.
Illustrative Example:
Find the HCF of 624 and 936.
Solution: 
Since both the numbers are even, therefore they are divisible by 2. On dividing, we obtain 312 and 468 as the quotients, which are also even. So, we divide them by 2. Now, the quotients obtained are 156 and 234 which are further divisible by 2,3 and 13. Therefore,
Required H.C.F. = Product of all the common divisors
= 2 x 2 x 2 x 3 x 13 = 312