Calculating LCM

Problem
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Solution:

Let X be a set of integers. 

|X| = N and xi is element of X where i is an element of the set {1,2, ... ,N} . Then,

LCM(x1,x2,.....,xN) = LCM(LCM(x1,x2,.....,xN-1),xN) and

LCM(x,y) = (x*y)/GCD(x,y) where x,y are any positive integer

LCM stands for Lowest Common Multiple. and GCD stands Greatest Common Divisor.Calculating GCD is a very efficient algorithm given by the great Euclid. It is called the grand daddy of all algorithm. The oldest algorithm that exists today and still play a great role in computer science.

Detail Work Out:

Let, X = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}

(Read the black font from top to bottom, and blue font from bottom to top)

LCM(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20) = LCM(LCM(1,2,3,4,5,6,7,8,9,1011,12,13,14,15,16,17,18,19),20)

LCM(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19) = LCM(LCM(1,2,3,4,5,6,7,8,9,1011,12,13,14,15,16,17,18),19)

LCM(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18) = LCM(LCM(1,2,3,4,5,6,7,8,9,1011,12,13,14,15,16,17),18)

LCM(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17) = LCM(LCM(1,2,3,4,5,6,7,8,9,1011,12,13,14,15,16),17)

LCM(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16) = LCM(LCM(1,2,3,4,5,6,7,8,9,1011,12,13,14,15),16)

LCM(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15) = LCM(LCM(1,2,3,4,5,6,7,8,9,1011,12,13,14),15)

LCM(1,2,3,4,5,6,7,8,9,10,11,12,13,14) = LCM(LCM(1,2,3,4,5,6,7,8,9,1011,12,13),14)

LCM(1,2,3,4,5,6,7,8,9,10,11,12,13) = LCM(LCM(1,2,3,4,5,6,7,8,9,1011,12),13)

LCM(1,2,3,4,5,6,7,8,9,10,11,12) = LCM(LCM(1,2,3,4,5,6,7,8,9,10,11),12)

LCM(1,2,3,4,5,6,7,8,9,10,11) = LCM(LCM(1,2,3,4,5,6,7,8,9,10),11)

LCM(1,2,3,4,5,6,7,8,9,10) = LCM(LCM(1,2,3,4,5,6,7,8,9),10)

LCM(1,2,3,4,5,6,7,8,9) = LCM(LCM(1,2,3,4,5,6,7,8),9) 

LCM(1,2,3,4,5,6,7,8) = LCM(LCM(1,2,3,4,5,6,7),8)

LCM(1,2,3,4,5,6,7) = LCM(LCM(1,2,3,4,5,6),7)

LCM(1,2,3,4,5,6) = LCM(LCM(1,2,3,4,5),6) 

LCM(1,2,3,4,5,6) = LCM(60,6) = (60*6)/GCD(60,6) = 60

LCM(1,2,3,4,5) = LCM(LCM(1,2,3,4),5)

LCM(1,2,3,4,5) = LCM(12,5) = (12*5)/GCD(12,5) = 60

LCM(1,2,3,4) = LCM(LCM(1,2,3),4)

LCM(1,2,3,4) = LCM(6,4) = (6*4)/GCD(6,4) = 12 

LCM(1,2,3) = LCM(LCM(1,2),3) 

LCM(1,2,3) = LCM(2,3) = (2*3)/GCD(2,3) = 6 

Now we know,

LCM(1,2) = (1*2)/GCD(1,2) = 2/1 = 2

So, now we calculate the whole thing backwards. (As like it is done in recursion in programming). It takes N-1 steps.