I'm trying to solve pretty complex problem with number theory and set of numbers.

To make the problem more clear we are going to define $GCD(a, b)$ as the greates number that divides both $a$ and $b$ and $LCM(a, b)$ as least common multiple of $a$ and $b$. For my problem I want to calculate both $GCD(x_1,\dots, x_n)$ and $LCM(x_1,\dots, x_n)$ for set of numbers $x_{i}\leq 300000$. But because we may have up to $10^5$ numbers I need to calculate this number modulo $p = 10^9 + 7$

My question is: If we are using Euclidean algorithm is it true that $$GCD(A, B) \text{ mod } p = GCD(A\text{ mod }p, B\text{ mod } p ) \text{ mod }p$$ $$\text{and}$$ $$LCM(A, B) \text{ mod } p = LCM(A\text{ mod }p, B\text{ mod } p ) \text{ mod }p$$

If we show that this is correct we can easily calculate those values in fast timing using the euclidean fast-gcd algorithm.

  • 1
    $\begingroup$ Which programming competition is this? "modulo 10^9 + 7" sounds very much like Project Euler. $\endgroup$ – gnasher729 Aug 7 '17 at 19:10
  • $\begingroup$ It is not part of programing contests, it is just similar exercise for practice available on one site $\endgroup$ – someone12321 Aug 7 '17 at 19:12
  • $\begingroup$ Please credit the source of the problem. A useful way is to link to the page on the site where you got this question from. $\endgroup$ – D.W. Aug 7 '17 at 19:27

$GCD$ and $LCM$ do not depend on an algorithm, they are mathematical functions on pair of integers.

The first statement is false. A counterexample: $$GCD(10, 17)\bmod{7} = 1 \bmod 7 = 1$$ but $$GCD(10 \bmod{7}, 17\bmod{7}) \bmod{7} = GCD(3, 3) \bmod 7 = 3 \bmod 7 = 3$$

The second is also false $$ LCM(12, 18) \bmod 7 = 36 \bmod 7 = 1$$ but $$ LCM(12 \bmod 7, 18 \bmod 7) \bmod 7 = LCM(5, 4) \bmod 7 = 20 \bmod 7 = 6$$

  • $\begingroup$ Thanks for the answer, is there a way to eficently calculate lcm of set of 100000 numbers modulo p? $\endgroup$ – someone12321 Aug 6 '17 at 20:22
  • $\begingroup$ What exactly do you want to compute? $GCD/LCM(x, y) \bmod p$ of $10^5$ numbers, and so $10^{10}$ pairs? $\endgroup$ – fade2black Aug 6 '17 at 20:28
  • $\begingroup$ Noo i want to calculate two numbers, one number is the gcd of this set of numbers modulo p and the other one is lcm of those same numbers modulo p $\endgroup$ – someone12321 Aug 6 '17 at 20:30
  • $\begingroup$ In fact computing $LCM$ is reduced to computing $GCD$ since $LCM(x, y) = \frac{xy}{GCD(x,y))}$, so you need a fast $GCD$ algorithm. In such cases I consult to "The Art of Computer Programming" Volume 2, "Seminumerical Algorithms" by D. Knuth. $\endgroup$ – fade2black Aug 6 '17 at 20:34
  • 1
    $\begingroup$ I know the euclidean algorithm for calculating $GCD$ very fast, $GCD(x, y) = gcd(y, x mod y)$, but I dont know how to make it work with this modulo $\endgroup$ – someone12321 Aug 6 '17 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.