Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
4  
Well, you have $$(a-x)(b-y) \equiv 0 \mod pq$$ –  Joel Cohen Feb 23 '12 at 15:04

2 Answers 2

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|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|improve this answer

Your Answer

 
discard

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.