I got really confused by Chinese remainder theorem.
For example, for the following quadratic function $$x^2\equiv4\pmod{30}$$ If I choose $m = 3$ and $n = 10$. They are coprime numbers, then I apply the Chinese remainder theorem to find the solutions. Of course, they are wrong.
But why? Can someone help please?
Here are the steps:
$x^2=4$ mod 3 gives x = 1, 2
$x^2=4$ mod 10 gives x = 2, 8
find the gcd=uv+mn 10 = 3*3 + 1 1 = 10 - 3*3
let m = 10, n = 3
(1, 2): 1*(1-10) + 3*(1+3*3) = 21 mod 30
(1, 8): 1*(1-10) + 8*(1+3*3) = 11
(2, 2): 2*(1-10) + 2*(1+3*3) = 2
(2, 8): 2*(1-10) + 8*(1+3*3) = 2
My solutions are therefore: 2, 21, 11
Hint $\ $ mod $3$ and $10$ the two solutions $\,x\equiv \pm2\,$ lift to four solutions mod $30$. Besides the obvious "constant" solutions $\,x\equiv 2\,$ mod $3$ and mod $10$ which lifts to $\,x\equiv 2\pmod{30}$ and its negative $\,x\equiv -2\pmod{30}$, we get two more solutions from the cases where they have opposite signs for each modulus, e.g. $\,x\equiv 2\pmod3$ and $\,x\equiv -2\pmod{10}$. Solving we have $\,x = -2 + 10k,\,$ so ${\rm mod}\ 3\!:\ 2 \equiv x \equiv -2+10k$ $\iff 10k\equiv 4\iff \color{#c00}{k\equiv 1},\,$ so $\,x\equiv -2+10(\color{#c00}1)\equiv 8\pmod{30}.\,$ The other opposite sign solution is just its negative $\, x\equiv -8\pmod{30}$