1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.