System of (non-linear) congruence equations

Question

I got a system of two congruence equations where one of them is non-linear.

\begin{cases} 2*x^2 + 5 \equiv 4\ (\textrm{mod}\ 11) \\ x \equiv 3\ (\textrm{mod}\ 13) \end{cases}

My idea was to rewrite the first equation like this:

$2*x^2 \equiv 10\ (\textrm{mod})\ 11$

And then use the chinese reminder theorem to find solutions to this equations:

\begin{cases} x \equiv 10\ (\textrm{mod}\ 11) \\ x \equiv 3\ (\textrm{mod}\ 13) \end{cases}

This gives me the solution $x=120$ which does not work for the first equation of my original equations. I then tried to add $11*13$ to this solution until the double of a square number occurs. But it looks like this doesn't work. Can you give me some advice on how to solve such an equation?

Answer 1

First of all, from the Bézout identity $6\cdot 2+(-1)\cdot 11=1,$ we see that $6\equiv 2^{-1}\pmod{11},$ so that $$x^2\equiv6\cdot 2x^2\equiv6\cdot10\equiv60\equiv5+5\cdot11\equiv5\pmod{11}.$$

Next, we consider the squares modulo $11$: $$0^2\equiv 0\pmod{11}\\1^2\equiv 10^2\equiv 1\pmod{11}\\2^2\equiv 9^2\equiv 4\pmod{11}\\3^2\equiv 8^2\equiv 9\pmod{11}\\4^2\equiv 7^2\equiv 5\pmod{11}\\5^2\equiv 6^2\equiv 3\pmod{11}.$$ Since $x\equiv4\pmod{11}$ and $x\equiv7\pmod{11}$ are the only solutions to $x^2\equiv5\pmod{11},$ then we can instead use the CRT on the systems $$\begin{cases}x\equiv 4\pmod{11}\\ x\equiv 3\pmod{13}\end{cases}$$ and $$\begin{cases}x\equiv 7\pmod{11}\\ x\equiv 3\pmod{13}\end{cases}$$ to obtain the desired solutions.

To tackle the first system, we begin with the Bézout identity $$6\cdot 11+(-5)\cdot13=66+-65=1,$$ then find that $$66\cdot3+-65\cdot4\equiv 198+-260\equiv -62\equiv 81\pmod{143}.$$ Similarly, the second system shows that $$66\cdot3+-65\cdot7\equiv 198+-455\equiv -257\equiv -114\equiv 29\pmod{143}.$$

Thus, our only possible solutions are $x\equiv 81\pmod{143}$ and $x\equiv 29\pmod{143},$ both of which can quickly be verified to be true.

---

As an alternative, we could use $x\equiv 3\pmod{13}$ to obtain the general solution $x=3+13n$ where $n$ is some integer, and substitute it into the other congruence. I would still begin by transforming the other into the equivalent congruence $$x^2\equiv 5\pmod{11},$$ at which point substitution yields the following (equivalent) congruences: $$(3+13n)^2\equiv 5\pmod{11}\\9+78n+169n^2\equiv 5\pmod{11}\\(-2+11)+(1+7\cdot11)n+(4+15\cdot11)n^2\equiv 5\pmod{11}\\-2+n+4n^2\equiv 5\pmod{11}\\4n^2+n\equiv 7\pmod{11}\\3\cdot4n^2+3\cdot n\equiv 3\cdot7\pmod{11}\\12n^2+3n\equiv 21\pmod{11}\\(1+11)n^2+(-8+11)\cdot n\equiv (10+11)\pmod{11}\\n^2+(-8)n\equiv10\pmod{11}\\n^2+2\cdot(-4)\cdot n\equiv 10\pmod{11}\\n^2+2\cdot(-4)\cdot n+(-4)^2\equiv 10+(-4)^2\pmod{11}\\\bigl(n+(-4)\bigr)^2\equiv 26\pmod{11}\\\bigl(n+(-4)\bigr)^2\equiv 4+2\cdot11\pmod{11}\\\bigl(n+(-4)\bigr)^2\equiv 4+2\cdot11\pmod{11}\\\bigl(n+(-4)\bigr)^2\equiv 4\pmod{11}$$ At this point, we again consider the squares modulo $11,$ as we did in the previous approach, to see that $n+(-4)\equiv2\pmod{11}$ and $n+(-4)\equiv9\pmod{11}$ are the only possibilities, meaning that $n\equiv 6\pmod{11}$ or $n\equiv 2\pmod{11}.$

Thus, either $$x=3+13(6+11k)=3+78+143k=81+143k$$ or $$x=3+13(2+11k)=3+26+143k=29+143k$$ for some integer $k,$ meaning that $x\equiv81\pmod{143}$ or $x\equiv29\pmod{143},$ as desired.

Answer 2

HINT:

$$x\equiv3\pmod{13}\implies x-3=13l\\2x^2\equiv2(3+13l)^2\equiv18+156l+338l^2\equiv-1\pmod{11}\implies 8+2l-3l^2\equiv0\pmod{11}$$

Answer 3

From $x\equiv 3\mod 13$ we conclude that $$x^2\equiv 9\mod 13$$define $y=x^2$, therefore $$2y+5\equiv 4\mod 11\\y\equiv 9\mod 13$$applying Chinese Remainder Theorem on the above set of equations we conclude that $$y\equiv126\mod 143$$therefore $$x^2\equiv 126\mod 143$$among which the answers with $x\equiv 3\mod 13$ are acceptable. Now let $$x=143k+r\quad,\quad 0\le r<143$$by substitution we obtain $$x^2\equiv r^2\equiv 126 \mod 143$$Numerical simulations show that the only possible values for $r$ are $$29\quad 62\quad 81\quad 114$$also the constraint $x\equiv 3\mod 13$ imposes that $$r\equiv 3 \mod 13$$ which leaves us with $$r=29\\r=81$$therefore we if an answer $x$ exists, it must be either$$x\equiv 29\mod 143$$or $$x\equiv 81\mod 143$$There is one final step. To show that these answers are also sufficient condition, we show that they satisfy the primary equations of the question. Let $x=143k+29$ therefore $$2x^2+1\equiv 2\times29^2+1\equiv 2\times (-4)^2+1\equiv 33\equiv 0\mod 11$$also for $x=143k+81$ we have $$2x^2+1\equiv 2\times81^2+1\equiv 2\times (-7)^2+1\equiv 99\equiv 0\mod 11$$

Conclusion

The only answers are$$x\equiv 29\text{ or }81\mod 143$$