Why is answer 2 not right?

To apply Chinese Remainder Theorem to solve a system of modular equations all the moduli have to be pairwise relatively prime. Given the following system of modular equations:

$x\equiv 3\pmod 3$

$x\equiv 5\pmod 9$

$x\equiv 4\pmod 5$

we should only select the following in order to apply Chinese Remainder Theorem:

$x\equiv 5\pmod 9$

$x\equiv 4\pmod 5$.

Why is this the case? I think $x\equiv 3\pmod 3$ and $x\equiv 4 \pmod5$ should also be right since you can't fully solve the system of modular equations either way.

  • $\begingroup$ Welcome to MSE. It is in your best interest that you type your questions (using MathJax) instead of posting links to pictures. $\endgroup$ Mar 14 '20 at 7:46
  • 2
    $\begingroup$ Tosolve this system, I'd rather consider only the mod 3 and mod 9 equation as only this pair implies the correct answer: that no solution exists $\endgroup$ Mar 14 '20 at 7:47
  • $\begingroup$ The first two congruences contradict. The first means that $x$ is divisible by $3$ , the second that it is not. $\endgroup$
    – Peter
    Mar 14 '20 at 9:23
  • $\begingroup$ That quiz question is very poorly posed. It is not clear if they are trying to get you to select two equations to which CRT applies (i.e. with coprime moduli), or whether they are attempting to get you to select the two equations which prove the system of three equations is unsolvable by the generalized solvability criterion. $\endgroup$ Mar 14 '20 at 17:04

@alramdkwan, first, welcome to MSE.

Now, concerning your question, I think that it already implies that there is no solution exists because:

  1. $x \equiv 3 \pmod{3}$ means $x$ is divisible by 3
  2. $x \equiv 5 \pmod{9}$ means $x$ is not divisible by 3

The two conditions above yield the result of no $x$,

About your solution, I think it is true that in two cases you have two answers. But this is not incorrect. It rather leads you to the conclusion that this system has no solution.

  • $\begingroup$ Or you can say $x \equiv 5 \pmod 9 \implies x \equiv 2 \pmod 3$. $\endgroup$ Feb 1 '21 at 1:22

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.