# A question on modular arithmetic

Assume that \begin{align*} a &\equiv x \pmod p \\ b &\equiv y\pmod q.\end{align*}

Does this imply an equation involving the numbers $a,b,x,y$ modulo $pq$? One possible example would be $$ab \equiv xy\mod pq$$

-
Not quite. Take $a = 0$, $x = p$, $b = 1$, and $y = q+1$. Then your suggestion gives $$0 \equiv (q+1)p \bmod pq$$ which doesn't have to be true! However, if you avoid picking anything that reduces to 0..? (Also, I'm guessing $p$ and $q$ are primes?) –  Alex Feb 23 '12 at 14:42
I don't think you can do better than $$ab\equiv (x\mod q)(y\mod p)\mod pq$$ since the value of $x\mod p$ and $y\mod q$ don't tell you much about $x\mod q$ and $y\mod p$. –  Alex Becker Feb 23 '12 at 14:54
Well, you have $$(a-x)(b-y) \equiv 0 \mod pq$$ –  Joel Cohen Feb 23 '12 at 15:04

Here is an equivalent question: given that $(a - x)$ is a multiple of $p$ and $(b - y)$ is a multiple of $q$, can we conclude that something is a multiple of $pq$? The answer is yes: $(a - x)(b - y)$, $(a - x)q$, and $p(b - y)$ all must be multiples of $pq$. So, among other things, we have:

\begin{align*}(a - x)(b - y) &\equiv 0\phantom{0} \pmod{pq}\\ aq &\equiv xq \pmod {pq}\\ pb &\equiv py \pmod{pq}.\end{align*}

The first equation might look nicer if we multiply it out:

$$ab + xy \equiv ay + xb \pmod{pq}.$$

-

There is similiar law $$a \equiv b\pmod n \\c \equiv d\pmod n$$ imply $$ac \equiv bd\pmod n \\a+c \equiv b+d\pmod n$$

-