# 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?

## One Answer

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

### If $sigma in A_n$ has a split conjugacy class, then $tau sigma tau^{-1}$ is not conjugate to $sigma$ for odd $tau$

0  Asked on November 27, 2020 by jskattt797

### Irreducible polynomial equations from equations of algebraic functions in two variables?

2  Asked on November 27, 2020 by iv_

### Solving two coupled ODEs without use of complex numbers

1  Asked on November 27, 2020 by daniels-krimans

### How many words of length $10$ are there in which not all of the vowels A, E, I, O, U appear?

1  Asked on November 27, 2020 by jos-pedro-ferreira

### Cardinality of finite sequences of infinite set

1  Asked on November 27, 2020 by avir_12

### Valuation of polynomials

1  Asked on November 27, 2020 by muselive

### Existence of the Eigenvalues of an Idempotent Mapping

2  Asked on November 27, 2020 by v-elizabeth

### resolution – satisfiability of formula (edit: renaming clause variables)

1  Asked on November 27, 2020 by harshatech2012

### Satisfying an equation in natural numbers

1  Asked on November 26, 2020 by luyw

### Showing $x^2sin frac {1}{x}$ is surjective

2  Asked on November 26, 2020 by mathfun

### Computing the area between 2 curves

1  Asked on November 26, 2020 by diego-lima

### limit of multivariable function as x,y approach to infinity

1  Asked on November 26, 2020 by simon

### Finding Solutions to a System of Diophantine Equations

0  Asked on November 26, 2020 by godorgovern

### Could it be argued that the set containing only the origin is a “vector space”?

1  Asked on November 26, 2020 by financial_physician

### If $f_n(x)$ uniformly converge to a positive function, then $dfrac{1}{f_n(x)}rightrightarrowsdfrac{1}{f(x)}$?

2  Asked on November 26, 2020 by user823011

### Doubt on showing that when $p$ is prime, the only unipotent class is $p-1$?

1  Asked on November 25, 2020 by billy-rubina

### Solve $n < e^{6 sqrt{n}}$

3  Asked on November 24, 2020

### Evaluate integral $int (x^2-1)(x^3-3x)^{4/3} mathop{dx}$

3  Asked on November 24, 2020 by user801303

### Find all pairs of integers $(x, y)$ such that $x^3+y^3=(x+y)^2.$

1  Asked on November 23, 2020

### Integer solutions to $z^2=10x^2-2y^2$

3  Asked on November 22, 2020 by slave-of-christ

### Ask a Question

Get help from others!

© 2023 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP