# Calculating greatest common divisor and least common multiple modulo prime number

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.

• Which programming competition is this? "modulo 10^9 + 7" sounds very much like Project Euler. – gnasher729 Aug 7 '17 at 19:10
• It is not part of programing contests, it is just similar exercise for practice available on one site – someone12321 Aug 7 '17 at 19:12
• 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. – 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$$
• What exactly do you want to compute? $GCD/LCM(x, y) \bmod p$ of $10^5$ numbers, and so $10^{10}$ pairs? – fade2black Aug 6 '17 at 20:28
• 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. – fade2black Aug 6 '17 at 20:34
• 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 – someone12321 Aug 6 '17 at 20:36