# System of (non-linear) congruence equations

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?

• It is not true that $\,2x^2\equiv 10\,\Rightarrow\, x\equiv 10\pmod{11}\$ – Bill Dubuque Jan 5 '19 at 20:46

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.

• Thanks for your help! Is there a clever way to argument why your solution gives me all possible solutions $\pmod{143}$? – Johny Dow Jan 6 '19 at 10:10
• I've expanded on things a bit (and included an important point that I accidentally deleted earlier. Let me know if you still have any doubts about it, or specific questions. – Cameron Buie Jan 6 '19 at 15:36

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

• Thanks! Am I right that only trial and error leads to the values of r? – Johny Dow Jan 5 '19 at 21:40
• You're welcome. This is what I think so. Since the equation of $r$ is not linear, I also think that a straight forward calculation doesn't lead to the values of $r$ – Mostafa Ayaz Jan 5 '19 at 21:45
• @Johny Mostafa is correct. That's why it's better to deal with the squares at a smaller modulus, instead. – Cameron Buie Jan 5 '19 at 23:08

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

• Thanks for your help! Can you give me some further advice? Solving the quadratic equation $8+2l-3l^2\equiv0\pmod{11}$ gives me the solutions $x = 2 + 11n$ and $x = 6 + 11n$ but when I try to use those values in the actual equation the solution is wrong. – Johny Dow Jan 5 '19 at 21:45