Highest Common Factor

The Highest Common Factor (HCF) of two or more given numbers is the highest (or greatest) of their common factors. It is also known as Greatest Common Divisor (GCD).

Example: Find HCF of 18 and 48

We can find HCF of 18 and 48 by finding the highest common factors of 18 and 48.

Factors of 18 = 1, 2, 3, 6, 9, 18

Factors of 48 = 1, 2, 3, 4, 6, 8, 12, 16, 24, 48

Common factors of 18 and 48 = 1, 2, 3, 6 (6 is the highest of these common factors)

HCF = 6

HCF with Prime Factorization Method

HCF of numbers can also be found by prime factorization of the numbers.

Example: Find the HCF of 30 and 42.

Prime factors of 30 = 2 x 3 x 5

Prime factors of 42 = 2 x 3 x 7

Common factor of 30 and 42 = 2 x 3 = 6

Therefore, Highest common factor (H.C.F) of 30 and 42 = 56

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 70, 105 and 175.

Now we cannot divide further with common factor.

Multiply common factor to get HCF = 5 x 7 = 35

So, HCF of 70, 105 and 175 = 35

Example 2: Find the HCF of 91, 112 and 49.

Now we cannot divide further with common factor.

Multiply common factor to get HCF = 7

So, HCF of 91, 112 and 49 = 7

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 27 and 63

Explanation

Step1: Start dividing 63 by 27

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

Step 3: Now remainder is 0. So, further division is not possible and the last divisor 9 becomes the HCF of 27 and 63.

Note:

     1.   HCF of any two consecutive numbers is 1.

     2.   HCF of two consecutive even numbers is 2.

     3.   HCF of two consecutive odd numbers is 1.

     4.   HCF of two prime numbers is 1.

     5.   HCF of an even number and an odd number is 1.