So I had recently learned about Chinese Remainder theorem, and I got a Question to solve:
Find X if-
$X\equiv 1\bmod 2\\X\equiv 2 \bmod 3\\X\equiv 3 \bmod 4\tag*{}$
So I went on to find the solution modulus, $N=24$ & $N_1=12\\ N_2 = 8\\ N_3 = 6\tag*{}$
And now I just had to find the three inverse modulus, but for the first one
$12y_1\equiv 1 \bmod 2\tag*{}$ there's no $y_1$ satisfying the equation. I was stuck on this part. Please Highlight what I am doing wrong.
[Math] Unable to use Chinese Remainder Theorem on a question.
chinese remainder theoremcongruenceselementary-number-theory
Best Answer
The CRT doesn't apply right away because your moduli are not relatively prime. So there my not be a solution. If the last congruence had been $x\equiv 2 \pmod{4}$ then this would contradict the first congruence.
So in cases like this, one has to be observant and note that any solution to $x \equiv 3 \pmod{4}$ also satisfies $x\equiv 1 \pmod{2}$. So your first congruence is superfluous, and you can delete it. In more complicated cases, you can proceed in gimusi's answer. If you hit a contradiction doing that, then there is no solution.