1
$\begingroup$

I have a number $m = p\cdot q$, where $p,q$ are (odd) prime numbers. Is there any relation between $a \bmod{m}$ and $a \bmod p$ (or $a \bmod q$)?

P.S: Actually, I want to see is it possible to calculate modulo $m$ faster or not.

  • 0
    Indeed, this is a viable (and sometimes very efficient) strategy for long computations modulo composite numbers: perform the calculation mod $p$ and mod $q$ (which might allow various shortcuts because primes are nice), then synthesize the results into a single remainder.2012-06-17

0 Answers 0