Highest Common Factor(HCF)

ssc preparation, important competetion questions, current affairs of india, latest question asked in competetion papers,

Highest Common Factor(HCF)Highest Common Factor(HCF) of two or more numbers is the greatest number which divides each of them exactly.
Greatest Common Measure(GCM) and Greatest Common Divisor(GCD) are the other terms used to refer HCF.
Example : HCF of 60 and 75 = 15 because 15 is the highest number which divides both 60 and 75 exactly.
We can find out HCF using prime factorization method or by dividing the numbers or division method.

How to find out HCF using prime factorization methodStep 1: Express each number as a product of prime factors. (Reference: Prime Factorization)

Step 2: HCF is the product of all common prime factors using the least power of each common prime factor.
Example 1: Find out HCF of 60 and 75
Step 1 : Express each number as a product of prime factors.
60 = 2² × 3 × 5
75 = 3 × 5²
Step 2: HCF is the product of all common prime factors using the least power of each common prime factor.
Here, common prime factors are 3 and 5
The least power of 3 here = 3
The least power of 5 here = 5
Hence, HCF = 3 × 5 = 15
Example 2: Find out HCF of 36, 24 and 12Step 1: Express each number as a product of prime factors.
36 = 2² × 3²
24 = 2³ × 3
12 = 2² × 3
Step 2: HCF is the product of all common prime factors using the least power of each common prime factor.
Here 2 and 3 are common prime factors.
The least power of 2 here = 2²
The least power of 3 here = 3
Hence, HCF = 2² × 3 = 12
Example 3: Find out HCF of 36, 27 and 80step 1 : Express each number as a product of prime factors.
36 = 2² × 3²
27 = 3³
80 = 2⁴ × 5
Step 2 : HCF is the product of all common prime factors using the least power of each common prime factor.
Here you can see that there are no common prime factors.
Hence, HCF = 1

How to find out HCF - by dividing the numbers (shortcut method)Step 1: Write the given numbers in a horizontal line separated by commas.
Step 2: Divide the given numbers by the smallest prime number (write in the left side) which can exactly divide all the given numbers.
Step 3: Write the quotients in a line below the first.
Step 4: Repeat the process until we reach a stage where no common prime factor exists for all the numbers.
Step 5: We can see that the factors mentioned in the left side clearly divides all the numbers exactly and they are common prime factors. Their product is the HCF
Example 1: Find out HCF of 60 and 75

3	60,75
5	20,25
	4,5

We can see that the prime factors mentioned in the left side clearly divides all the numbers exactly and they are common prime factors. No common prime factor exists for the numbers came at the bottom.
Hence HCF = 3 × 5 = 15.
Example 2: Find out HCF of 36, 24 and 12

2	36,24,12
2	18,12,6
3	9,6,3
	3,21

HCF = 2 × 2 × 3 = 12.
Example 3: Find out HCF of 36, 24 and 48

2	36,24,48
2	18,12,24
3	9,6,12
	3,24

HCF = 2 × 2 × 3 = 12.

How to find out HCF using division method(shortcut method)To find out HCF of two given numbers using division method,
Step 1: Divide the larger number by the smaller number.
Step 2: Divisor of step 1 is divided by its remainder.
Step 3: Divisor of step 2 is divided by its remainder. Continue this process till we get zero as remainder.
Step 4: Divisor of the last step is the HCF.
To find out HCF of three given numbers using division method,
Step 1: Find out HCF of any two numbers.
Step 2: Find out the HCF of the third number and the HCF obtained in step 1.
Step 3: HCF obtained in step 2 will be the HCF of the three numbers.
In a similar way as explained for three numbers, we can find out HCF of more than three numbers also using division method.