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

Add your own answers!

Related Questions

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


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


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

3  Asked on November 24, 2020


Ask a Question

Get help from others!

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