Chinese Remainder Theorem Backwards

837 Views Asked by At

I was reading a description of the CRT which went like this

$x = a \mod p$
$x = b \mod q$ has a unique solution for $x \mod pq$

It also said - The reverse direction is trivial. Give $x \mod pq$ we can reduce it to $\mod p$ & $\mod q$

What are the steps to do the reverse. If I have an equation for $\mod pq$, what do I to obtain equations in $\mod p$ & $\mod q$?

1

There are 1 best solutions below

6
On

I think it's a lot easier to understand with an example. Suppose we are told $x\equiv 7 \bmod 15$, then we have $x\equiv 7 \bmod 3$ and $x\equiv 7\bmod 5$. Of course we can "reduce" this to $x\equiv 1 \bmod 3$ and $x\equiv 2\bmod 5$.

Hopefully this clears it up.