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

- Finding the LCM .
- (LCM % m)^k=A.
- 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

0 Asked on November 27, 2020 by jskattt797

2 Asked on November 27, 2020 by iv_

1 Asked on November 27, 2020 by daniels-krimans

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

1 Asked on November 27, 2020 by avir_12

2 Asked on November 27, 2020 by v-elizabeth

1 Asked on November 27, 2020 by harshatech2012

first order logic formal proofs logic predicate logic satisfiability

1 Asked on November 26, 2020 by luyw

2 Asked on November 26, 2020 by mathfun

1 Asked on November 26, 2020 by diego-lima

1 Asked on November 26, 2020 by simon

0 Asked on November 26, 2020 by godorgovern

1 Asked on November 26, 2020 by financial_physician

2 Asked on November 26, 2020 by user823011

1 Asked on November 25, 2020 by billy-rubina

3 Asked on November 24, 2020 by user801303

1 Asked on November 23, 2020

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

combinatorics diophantine equations elementary number theory integers

Get help from others!

Recent Answers

- haakon.io on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

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