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

Mathematics Asked on January 3, 2022

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?

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 = dcdot(frac{LCM}d - ell frac md)$$ and we can write: $$x=dcdotleft(frac{LCM}{d} bmod frac mdright) = dcdotleft(LCM(frac{a_1}d,ldots,frac{a_n}d)bmod frac mdright).$$

Answered by Klaas van Aarsen on January 3, 2022

## Related Questions

### Do infinitely many points on earth have the same temperature as their antipodal?

1  Asked on December 27, 2021 by roberto-faedda

### Missing argument in the proof of the closedness of the graph of a morhpism between algebraic varieties

1  Asked on December 27, 2021 by redundant-aunt

### How to deal problems in finding real roots of a polynomial?

1  Asked on December 27, 2021

### When can you factor out terms from a double integral?

2  Asked on December 27, 2021

### Compactness Interpretation?

1  Asked on December 27, 2021

### Show $h(x) in F[x]$

1  Asked on December 27, 2021

### Differentiating under the Integral with Carathéodory.

0  Asked on December 27, 2021 by tom-collinge

### Are functional differentials just regular differentials on the manifold of functionals?

0  Asked on December 27, 2021

### Union of two non empty and mutually exclusive finite sets is finite

0  Asked on December 27, 2021

### Do sparse graphs contain regular pairs?

1  Asked on December 27, 2021 by alpmu

### Brouwer’s fixed point theorem and the one-point topology

1  Asked on December 27, 2021 by r-srivastava

### Definition of second derivative as a limit

5  Asked on December 27, 2021 by kiwifruit

### Top 10 math mnemonics

5  Asked on December 27, 2021 by almagest

### Unimodular Matrix Inverse Proof Confusion

2  Asked on December 27, 2021

### Distance between two lines $L_1:> x+y+z=6,> x-2z=-5$; $L_2:> x+2y=3,> y+2z=3$

3  Asked on December 27, 2021

### Does $lim_{(x,y)to (a,b)} frac{f(x)}{g(x,y)}$ that equals to $lim_{(x,y)to (a,b)} frac{g(x,y)}{f(x)}$ mean that the limit equals to 1?

3  Asked on December 27, 2021 by possible

### What is the maximum value of the $4 times 4$ determinant composed of 1-16?

1  Asked on December 27, 2021

### Need help with a Fourier series question

0  Asked on December 27, 2021

### Characterization of Integral Domains

1  Asked on December 27, 2021

### Unique solution to an Initial Value Problem

2  Asked on December 27, 2021