# HCF - Highest Common Factor

## HCF - Highest Common Factor

##### HCF or GCD or GCM:

Highest Common Factor also called as Greatest Common Measure(GCM) or Greatest Common Divisor(GCD). H.C.F of two or more numbers is the greatest number that can exactly divide each one of the number.

##### Example:

Say we have 2 numbers 4,8. The numbers that can divide 4 and 8 are 2,4. Here 4 is the highest number that can exactly divide both 4 and 8 , so 4 is the HCF of 4,8. H.C.F can be calculated by any of the following methods,

##### Factorization Method:

Express each one of the numbers as product of prime factors. The product of least powers of common prime factors gives HCF.

##### Example:

Greatest Common Measure of 36, 90, 72.

###### Step1:

Express the numbers as product of prime factors. 36 = 22 ×32 90 = 2× 5× 32 72 = 23 × 32

###### Step2:

Take the prime numbers with least power and is present in all sets. 2 and 3 are the prime number common to all given numbers. The least power of 2 in the set is - 2 The least power of 3 in the set is - 32

###### Step3:

Product of the numbers taken. 32 ×= 2 = 9 × 2 = 18 So 18 is the GCD(Greatest Common Divisor) of the numbers.

##### Division Method:

Two find the HCF of two given numbers, divide the largest by the small number, then divide the dividend by the remainder. Repeat this until remainder is 0. The last dividend is the HCF of the two numbers.

##### Example: HCF of 27 & 36
###### Step1:

Divide 36/27 -> remainder = 9

##### Step2:

Divide dividend by remainder 27/9 -> remainder = 0 So the HCF or GCD(greatest common Divisor) of 27 and 36 is 9 For 3 numbers, calculate the HCF or greatest common measure(GCM) of 2 numbers, then HCF of the result with 3rd number.