Highest Common Factor

The Greatest Common Divisor (GCD) is also known as the Greatest Common Factor (GCF), Highest Common Factor (HCF), Greatest Common Measure (GCM), or Highest Common Divisor.

HCF with Prime Factorization Method

Example: Find the HCF of 15 and 35.

Prime factors of 15 = 3, 5

Prime factors of 35 = 5, 7

Common factor of 15 and 35 = 5

Therefore, Highest common factor (H.C.F) of 15 and 35 = 5

HCF by Division Method

Step1: Divide the two given numbers together by their common prime factors.

Step2: Stop dividing when there is no common prime factor left.

Step3: Multiply the common prime factors to find the HCF.

Example 1: Find the HCF of 12 and 18.

Now we cannot divide further with common factor.

Multiply common factor to get HCF = 2 x 3 = 6

So, HCF of 12 and 18 = 6

Example 2: Find the HCF of 12, 36 and 48.

Now we cannot divide further with common factor.

Multiply common factor to get HCF = 2 x 2 x 3 = 12

So, HCF of 12, 36 and 48 = 12

HCF by Long Division Method

The method of long division is more useful for large numbers.

Step1: Identify the larger number from the given two numbers and divide the larger number by the smaller number.

Step2: Now remainder become divisor and the previous divisor become the dividend. Divide the new dividend with new divisor.

Step3: Continue this process till we get remainder as 0.

Step4: The last divisor in this process is the H.C.F of the two numbers

Example: Find HCF of 18 and 30

Step1: Start dividing 30 by 18

Step2: Now, remainder 12 becomes the divisor and previous divisor 18 has become the dividend. Divide 18 by 12.

Step3: Now the new remainder 6 becomes the divisor and previous divisor 12 has become the dividend. Divide 12 by 6.

Step4: Now remainder is 0. So, further division is not possible and the last divisor 6 becomes the HCF of 18 and 30.