Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$$

share|cite|improve this question
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
up vote 3 down vote accepted

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}.$$

share|cite|improve this answer

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 $$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.