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.
Calculating greatest common divisor and least common multiple modulo prime number
number theory;modular arithmetic