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)

Example: Find the greatest number, which will divide 260, 281 and 303, leaving 7, 5 and 4 as remainders respectively.  

Ans: We have to find the HCF of (260 - 7, 281 - 5, 303 - 4) = HCF (253, 276, 299) = 23

Formula 4: When A, B, C are divided by N then the remainder is same in each case then N = HCF of any two of (A-B, B-C, C-A)

Example: Find the greatest number by which if we divide 740, 838 and 985, then in each case the remainder is the same.

 Ans: Given number is HCF (838 - 740, 985 - 838) = 49

Important result:

If we divide the given numbers with their HCF, the quotients must be co-primes with each other.  

Let us assume two numbers A, B.   Take A = ah and B = bh where a,b are co-primes with each other and h is the highest common factor of the two numbers. 

Now LCM (A, B) = abh.  (because h is the HCF of two given numbers, when we divide A, B with h, the quotients are coprimes. So LCM is equal to the product of h, a, b).

Now we can observe that A x B = ah x bh = abh x h = LCM (A, B) x HCF (A, B)