LCM or Least common factor and Highest common factor (HCF)or Greatest common divisor (GCD)

LCM is defined as the least number which is divisible by all the given divisors.  Take 4,6 as two divisors which divide 12, 24, 36... perfectly with no remainder.  So 12, 24, 36 are called common multiples of 4 and 6.  In other words, 4 and 6 are factors of all these number.  Of all these common multiples, 12 is the least number.  So we can say 12 is Least common multiple of all the given numbers or LCM of 4, 6.

Finding LCM: 

There are two ways to find LCM.  First one is division method, second one is Factorization method.  

1. Division Method: LCM of 15, 18, 27

In division method we have to continue the division until the numbers in the last row become co - primes with each other.  So LCM = 3 x 3 x 5 x 2 x 3 =270

2. Factorization Method: 

Here we can write all the given numbers in their prime factorization format.

15 = 3 x 5

18 = 2×32

27 = 33

Now take all primes number the given numbers and write their maximum powers. So LCM of 15, 18, 27 = 2×33×5= 270

Formula 1: If r is the remainder in each case when N is divided by x, y, z then the general format of the number is N= K x [LCM (x, y, z)] + r here K is a natural number

Example: A teacher when distributed certain number of chocolates to 4 children, 5 children, 7 children, left with 1 chocolate.  Find the least number of chocolates the teacher brought to the class

Ans:  N = K (LCM (4, 5, 7) + 1 = 140K + 1.  Where K = natural number.  When we substitute K = 1, we get the least number satisfies the condition. So minimum chocolates = 141

 

Formula 2: If x1,y1,z1 are the remainders when N is divided by x, y, z and x−x1=y−y1=z−z1=a then the general format of the number is given by N= K x [LCM (x, y, z)] - a

Example: When certain number of marbles are divided into groups of 4, one marble remained.  When the same number of marbles are divided into groups of 7 and 12 then 4, 9 marbles remained. If the total marbles are less than 10,000 then find the maximum possible number of marbles.

Ans:  In this case the difference between the remainders and divisors is constant.  i.e., 3. so  N = K (LCM (4, 7, 12) -  3 = 84K - 3.  Where K = natural number.  

But we know that 84K - 3 < 10,000 ⇒ 84 x 119  - 3 < 10,000 ⇒ 9996 - 3 = 9993

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,  24=23×3

Now HCF of 16, 24 = 23 ( 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)