# Chinese remainder theorem for quadratic equation

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

• Well, what were the incorrect solutions you found? Show your working a little more. – Parcly Taxel Nov 5 '16 at 17:16
• Show your work so we can see where the problem lies. Be aware that the two solutions $x\equiv \pm 2$ mod $3$ and $10$ lift to four solutions mod $30$. That is not wrong. – Bill Dubuque Nov 5 '16 at 17:17

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}$