Highest common factor (HCF)or Greatest common divisor (GCD)

HCF is the maximum divisor which divides all the given numbers exactly.  Let us say for 16, 24 there are several numbers i.e., 1, 2, 4, 8 divide them exactly. Of all these numbers 8 is maximum number so we could call 8 as HCF

Finding HCF:  

HCF can be found in two ways. Division Method and Factorization method.

Example: Find the HCF of 16, 24

Factorization Method: 

We need to write each number in its prime factorization format and take the prime numbers common to all given numbers and their minimum power.

16=24$16=2^4$,  24=23×3$24=2^3\times 3$

Now HCF of 16, 24 = 23$2^3$ ( we must not consider 3 because 16 does not contain the prime factor 3)

Division Method: 

Important formulas: 

Formula 3: if a, b, c are the remainders in each case when A, B, C are divided by N then N = HCF (A-a, B-b, C-c)