How do I find the value of $\operatorname{LCM} (a_1^k,a_2^k, \ldots ,a_n^k) \pmod {m}$?

Question

LCM can be upto or greater than $10^{50}$. $k$ and $m$ are upto $10^9$.

My current approach is

1. Finding the LCM .
2. (LCM % m)^k=A.
3. A % m.

This is working but takes a long time in finding LCM using GCD. Is there any other way?

Answer 1

Hint: there is no need to actually calculate $LCM(a_1,\ldots,a_n)$. We only have to find $LCM \bmod m$. Instead calculate $d=GCD(a_1,\ldots,a_n,m)$.

Let $x = LCM(a_1,\ldots,a_n) \bmod m$. This means that $x = LCM - \ell m$ for some integer $\ell$. The right hand side is divisible by $d$, therefore $x$ is divisible by $d$ as well.
So we have $x = d\cdot(\frac{LCM}d - \ell \frac md)$ and we can write: $$x=d\cdot\left(\frac{LCM}{d} \bmod \frac md\right) = d\cdot\left(LCM(\frac{a_1}d,\ldots,\frac{a_n}d)\bmod \frac md\right).$$