Search code examples
mathlcm

LCM of n numbers modulo 1000000007

I have to find LCM of n numbers MODULO 10^9+7.My approach is find LCM of two numbers and then MOD them.Then take the LCM of next element and the answer obtained from the previous iteration and MOD them.Do this for all elements.Is it wrong ?

Solution

  • Yes, it is wrong. I have been working on a similar problem.

    You must be familiar with the following property of MOD:

    PROPERTY 1: (a*b*c*d...*p*q) % MOD = (a%MOD)(b%MOD)(c%MOD).....(q%MOD);

    but this is not the case with LCM.

    LCM(a,b)=a*b/GCD(a,b).

    LCM(LCM(a,b),c)=LCM(a,b)*c/GCD(LCM(a,b),c).

    Whenever LCM becomes greater than the MOD, the above mentioned property gets destroyed. You must try to find LCM in terms of products of different numbers in numerator only.

    This can be done by factorizing all the numbers and keeping the record of highest powers of various factors.

    LCM = (2^a)(3^b).... Now you can easily multiply them iteratively and also keep the limit under MOD by using property 1.