1

If I have a value:

A mod P, where P is a prime number, and A=a*b*c*d.... n elements.

Is there a way to transform this product modulo some other number which is co-prime to P.

Like A mod M.

Or will I have to do all multiplications over again?

what if there are multiple such queries?

if I have to find A mod M multiple times for many values of M. What will be the best method to do that? Also A becomes very large to handle. Of the range 10^100000. So the only method remains is doing all the multiplications over again? Or can we do better?

Salena
  • 638
  • 2
    Not after doing your reduction modulo $P$. That’s part of the content of the Chinese Remainder Theorem: that a number with given congruence class modulo $P$ can have any congruence class modulo $M$ if $M$ is coprime to $P$. – Lubin Aug 02 '13 at 17:11

1 Answers1

4

If $\gcd(P, M) = 1$, then the Chinese Remainder Theorem gives you a bijection between the congruence classes modulo $PM$, and the pairs of congruence classes modulo $P$ and modulo $M$. Which can be read as saying that knowing $A \pmod{P}$ tells you nothing about $A \pmod{M}$.

Andreas Caranti
  • 68,873
  • if I have to find A mod M multiple times for many values of M. What will be the best method to do that? Also A becomes very large to handle. Of the range 10^100000. So the only method remains is doing all the multiplications over again? Or can we do better? – Salena Aug 02 '13 at 17:48