# Modulo properties of two prime numbers

I am supposed to prove that x = y mod (p*q) <=> x = y mod p and x = y mod q with p and q are prime numbers. It somewhat sounds reasonable to me, but unfortunately I don't have any clue how to prove it.

-
Recall the definition for when two numbers are congruent modulo some number. Then prove for yourself that if two numbers are congruent modulo some product, they are also congruent modulo the factors of the product. Then prove for yourself that if two numbers are congruent modulo two different moduli, then they are congruent modulo the least common multiple of the moduli. Then apply these results, and you are done. – K.G. Jun 5 '14 at 11:15
@K.G. You really should’ve posted that as an answer… it surely would be an acceptable one (that is, from my point of view). – e-sushi Jun 5 '14 at 13:05

That the left hand side implies the right hand side is easy, it follows from the following fact:

$$x\equiv y \mod{pq}\ \Leftrightarrow pq \mbox{ divides }x-y \Rightarrow p \mbox{ divides } x-y \mbox{ and } q \mbox{ divides }x-y$$

And so $x\equiv y \mod{p}$ and $x\equiv y \mod{q}$

Now, the point here is argument can be "reversed" in the case that $p$ and $q$ are relatively primes (and actually they are since we are assuming that they are different, if they're not, we can't obtain the result), it is, if $x\equiv y \mod{p}$ and $x\equiv y \mod{q}$, then p $\mbox{ divides } x-y$ and $q \mbox{ divides }x-y$, and as $p$ and $q$ are relatively prime (this is a well known theorem in number theory) we have that $pq$ divides $x-y$, thus $x\equiv y \mod{pq}$.

This is the general version of theorem I've wrote before:

Let $a,b,n\in \mathbb{Z}$ and suppose that $a$ divides $n$ and $b$ divides $n$, then $ab$ divides $n\cdot \mbox{gcd}(a,b)$. This, in the case that $a,b$ are relatively prime, gives the result i'm reffering to (because in that case $\mbox{gcd}(a,b)=1$).

Here's a small proof of this fact. Let $n=as$ and $n=bt$, write $\mbox{gcd}(a,b)=g$, we know that there exists $x,y$ integers such that $ax+by=g$ (see this post), then, multiplying this expression by $n$, we obtain $n(ax)+n(by)=ng$, replacing adequately, we have $(bt)(ax)+(as)(by)=ng$ and rearranging, we finally obtain $(ab)(xt+ys)=ng$ so $ab$ divides $ng=n\cdot \mbox{gcd}(a,b)$.

-
Could you post the theorem you are reffering to? Or a link to it. – CGFoX Jun 6 '14 at 9:53
It's done, I've edited my answer. – Solid Snake Jun 6 '14 at 11:33