0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Well, what were the incorrect solutions you found? Show your working a little more. $\endgroup$ – Parcly Taxel Nov 5 '16 at 17:16
  • 1
    $\begingroup$ 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. $\endgroup$ – Bill Dubuque Nov 5 '16 at 17:17
0
$\begingroup$

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

$\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.