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.

  • 1
    Well, $\Bbb Z/ pq\Bbb Z\cong \Bbb Z/p\Bbb Z\times\Bbb Z/q\Bbb Z$ realized via $\Bbb Z\to\Bbb Z/p\Bbb Z\times\Bbb Z/q\Bbb Z:a\mapsto(a\bmod p,a\bmod q)$ with kernel $pq\Bbb Z$.2012-06-10
  • 1
    @anon, I'm not a mathematician, would you describe it a bit more (I'm not sure I got it or not).2012-06-10
  • 5
    Loosely speaking, if you reduce $(a\bmod pq)$ modulo $p$ (respectively modulo $q$), you will end up with $(a\bmod p)$ (respectively $(a\bmod q)$). Conversely, knowing $(a\bmod p)$ and $(a\bmod q)$ is necessary and sufficient to determine $(a\bmod pq)$ by the Chinese Remainder Theorem.2012-06-10
  • 0
    Yes, thanks, extra chars.2012-06-10
  • 6
    @Saeed: Take a look at the Wikipedia page on the [Chinese Remainder Theorem](http://en.wikipedia.org/wiki/Chinese_remainder_theorem#Case_of_two_equations). As for calculating mod $m$ quickly, the Euclidean algorithm is going to be much faster than trying to use CRT.2012-06-10
  • 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