# Solving non-linear congruence

$x^2+2x+2\equiv{0}\mod(5)$, $7x\equiv{3}\mod(11)$

My attempt:

$x^2+2x+2\equiv{0}\mod(5)$

$(x+1)^2\equiv-1\mod(5)$, we have $x+1\equiv-1\mod(5)$

since $5$ and $11$ are coprime. We have a solution in $\mathbb{Z}_{11}$

With $[3]$ represent $3$, $[13]$ works for $7x\equiv3\mod11$

so $[3]$ is the solution in $\mathbb{Z}_{55}$

General solution is $x=-2+k55$.

-
Wait, what do you mean by $\pmod 0$? And why does $(x-1)² \equiv -1 \pmod 5$ imply $(x-1)\equiv -1 \pmod 5$? It should be that $(x-1) \equiv +-2 \pmod5$. – awllower Feb 12 '13 at 5:54
Thank you for the typo!! – Paul Feb 12 '13 at 5:56

$\rm mod\ 5\!:\ 0 \equiv x^2+2x+2 \equiv x^2-3x+2 \equiv (x-1)(x-2)\:\Rightarrow\: x\equiv \color{#C00}1,\,\color{#0A0}2.$

$\rm mod\ 11\!:\ 7x\equiv 3\equiv 14\:\Rightarrow\:x\equiv 2.\$ Solving these congruences yields

• $\rm\ \ x\equiv 2\ mod\ 11,\ x\equiv \color{#0A0}2\ mod\ 5\,\Rightarrow \: x\equiv 2\ mod\ 55.\$

• $\rm\ \ x\equiv 2\ mod\ 11,\ x\equiv\color{#C00} 1\ mod\ 5\!:\, 1 \equiv x\equiv 2+11n\equiv 2+n\Rightarrow n\equiv -1,\,$ thus
$\rm\qquad\qquad\qquad\qquad\qquad\qquad\qquad\ \ x = 2 + 11(-1 + 5k)\equiv -9\equiv 46\ mod\ 55.$

-

As you said, $(x+1)² \equiv -1 \equiv 4 \pmod 5$, hence $(x+1)\equiv 2 or -2 \pmod 5$. Now, if $(x+1)\equiv -2 \equiv 3 \pmod 5$, then, since also $x\equiv 2 \pmod {11}$ is a solution to the last congruence, one solution is $x\equiv 2 \pmod {55}$. On the other hand, for $x\equiv 1 \pmod {5}$, we should solve for $x\equiv 2 \pmod {11}$. Using Chinese Reminder Theorem, we conclude that the other solution is given by $x\equiv 11-20\equiv -9 \pmod{55}$.
P.S. Here we might view CRT as a decomposition of rings. But in essence, it talks about finding integers $x_i$ such that $\Sigma _ia_ix_i \pmod b$ is a solution of the congruences $x\equiv a_i \pmod {b_i}$, where $b=\Pi_ib_i$.
Reference

-
Am I not clear enough? – awllower Feb 12 '13 at 6:09
But the solution is $2$ or $46\mod(55)$... – Paul Feb 12 '13 at 6:23
I see where I went wrong. Sorry here. – awllower Feb 12 '13 at 6:27