Highest Common Factor or HCF / Greatest Common Divisor or GCD

A number has limited number of factors unlike multiples, so out of these factors what is an HCF?

As the name suggests, HCF is the highest common factor of two or more numbers. In other words, HCF is the biggest number that can divide all the given numbers.

METHODS TO FIND HCF

There are two methods to find HCF / GCD:-

Prime factorization method
Long division method

Let’s discuss these methods in detail.

Prime factorization method:

Step 1: write prime factors of given numbers.

Step 2: HCF will be product of least common power of prime number present between / among given numbers.

Let’s understand it with the help of an example.

Example: What is the HCF of 18 and 36?

A.18

B.9

C.12

D.36

Answer: Option A

Explanation:

Step 1 :-

18= 2 x 3 x 3 = 2¹x 3²
36 = 2 x 2 x 3 x 3 = 2²x 3²

Step 2 :- least power of 2 is 1 and of 3 is 2

Hence 2 x 3²= 18 is required HCF.

You’ll find more questions to practice this method at the end of this article.

HCF by Long Division Method

To find the H.C.F. of the given number using long division method, we will follow the following steps:

We divide the bigger number by smaller one.
Divide smaller number of step 1 with remainder obtained in step 1.
Divide divisor of second step with remainder obtained in step 2.
We will continue this process till we get remainder zero and divisor obtained in end is the required H.C.F.

Example: Find the HCF of 288 and 600

Solution:

Follow the steps as follows: