1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thanks, this is perfect. One last thing, is the way that I did it considered valid? Or did I make some leaps in my logic? $\endgroup$ – Slade Aug 7 '17 at 3:47
  • 1
    $\begingroup$ @Slade To complete your proof you need to justify the inference $\,pq\mid (x-y)^2\,\Rightarrow\, pq\mid x-y.\ \ $ $\endgroup$ – Bill Dubuque Aug 7 '17 at 12:32
  • $\begingroup$ 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? $\endgroup$ – Slade Aug 7 '17 at 18:24
  • 1
    $\begingroup$ @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. $\endgroup$ – Bill Dubuque Aug 7 '17 at 18:28
  • $\begingroup$ Okay, understood! Thanks! $\endgroup$ – Slade Aug 7 '17 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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