# Chinese remainder theorem application

If I understand, since 3 and 5 are relatively prime, the Chinese Remainder Theorem says that $x \equiv_3 a$ and $x \equiv_5 b$ have a unique solution $x_1$ mod 15. For $c \not \equiv_3 a$ and $d \not \equiv_5 b$ , Chinese Remainder Theorem shows if $x \equiv_3 c$ and $x \equiv_5 d$ there is a unique solution $x_2$ mod 15

My question is under what conditions it is guaranteed that $x_1 \not \equiv_{15} x_2$ including the general case for any system of linear congruences with coprime moduli.

I am trying to prove an exercise that asks to show that for fixed n , the solvable congruences $x^2 \equiv_n a$ have the same number of solutions for any a. I assume gcd(a,n) = 1 , factorize n, use previous results to show fixed size systems of systems of linear congruences but an not sure if that proves the last step via CRT.

Thanks.

If $x_1\equiv a\pmod{3}$ and $x_2\equiv c\pmod{3}$ with $a\not\equiv c\pmod{3}$ then $x_1\not\equiv x_2\pmod{3}$ which in particular implies that $x_1\not\equiv x_2\pmod{15}$

For proof, consider the contrapositive statement that $x_1\equiv x_2\pmod{15}$

Then $x_1-x_2=15k=3(5k)$ and therefore $a\equiv x_1\equiv x_2\equiv c\pmod{3}$, a contradiction.

Note that in the case that $a\not\equiv c\pmod{3}$ or $b\not\equiv d\pmod{5}$ you will have $x_1\not\equiv x_2\pmod{15}$. The "and" was able to be relaxed.