# Relationship when some number divided by two different (relatively prime) divisors results in the same remainder

This is a clarification from Rosen's discrete mathematics book. It says that 'by the Chinese Remainder theorem' the following is true: if $x\equiv y \mod{p}$ and $x\equiv y \mod{q}$, then if p and q are relatively prime: $x\equiv y \mod{pq}$.

I know the Chinese Remainder theorem allows us to multiply relatively prime moduli together as long as we create a solution x in a certain form, but I don't see how this conclusion would follow.

I thought of doing it this way (may be wrong):

$x\equiv y \mod{q}$ is the same as $x-y\equiv 0 \mod{q}$

$x\equiv y \mod{p}$ is the same as $x-y\equiv 0 \mod{p}$

So we can write these equations as $x-y = k_1p = k_2q$ for some integers $k_1$ and $k_2$.

Then I multiply the equations to get $(x-y)^2 = k_1k_2pq$, and converting back to a congruence: $(x-y)^2\equiv 0 \mod{pq}$.

And then we can reduce it down to $(x-y)\equiv 0 \mod{pq}$ which is $x\equiv y \mod{pq}$

I am unsure if the above is a correct way to get to this conclusion, but even if it is correct I don't see how the chinese remainder theorem plays a role.

Thanks for the help!

It follows from the uniqueness of the CRT solution: $\,x\equiv y\pmod{pq}\,\Rightarrow\, x\equiv y$ mod $p$ and mod $q$ so it is a solution, and by CRT the solution is unique $\!\pmod{pq}$.
But there is no need to use CRT since $\,p,q\mid x-y\,\Rightarrow\, {\rm lcm}(p,q)=pq\mid x-y,\,$ by $\gcd(p,q)=1.\$ This is exactly how CRT uniqueness is usually proved, e.g. see here.
• @Slade To complete your proof you need to justify the inference $\,pq\mid (x-y)^2\,\Rightarrow\, pq\mid x-y.\ \$ – Bill Dubuque Aug 7 '17 at 12:32
• Is it enough to convert to a congruence $(x-y)^2\equiv 0\bmod{pq}$, and since we can multiply congruences, and we know that the only number multiplied by itself to result in 0 is 0, then $(x-y)\equiv 0\bmod{pq}$ as well? – Slade Aug 7 '17 at 18:24
• @Slade No, since e.g. mod $4$ we have $2^2\equiv 0,$ but $2\not\equiv 0.\$ It is true for squarefree moduli that $\,a^2\equiv 0\,\Rightarrow\, a\equiv 0\,$ but this requires proof. – Bill Dubuque Aug 7 '17 at 18:28