Vtgyjfy

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?

First of all, from the Bézout identity $6cdot 2+(-1)cdot 11=1,$ we see that $6equiv 2^{-1}pmod{11},$ so that $$x^2equiv6cdot 2x^2equiv6cdot10equiv60equiv5+5cdot11equiv5pmod{11}.$$

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

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

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

As an alternative, we could use $xequiv 3pmod{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^2equiv 5pmod{11},$$ at which point substitution yields the following (equivalent) congruences: $$(3+13n)^2equiv 5pmod{11}\9+78n+169n^2equiv 5pmod{11}\(-2+11)+(1+7cdot11)n+(4+15cdot11)n^2equiv 5pmod{11}\-2+n+4n^2equiv 5pmod{11}\4n^2+nequiv 7pmod{11}\3cdot4n^2+3cdot nequiv 3cdot7pmod{11}\12n^2+3nequiv 21pmod{11}\(1+11)n^2+(-8+11)cdot nequiv (10+11)pmod{11}\n^2+(-8)nequiv10pmod{11}\n^2+2cdot(-4)cdot nequiv 10pmod{11}\n^2+2cdot(-4)cdot n+(-4)^2equiv 10+(-4)^2pmod{11}\bigl(n+(-4)bigr)^2equiv 26pmod{11}\bigl(n+(-4)bigr)^2equiv 4+2cdot11pmod{11}\bigl(n+(-4)bigr)^2equiv 4+2cdot11pmod{11}\bigl(n+(-4)bigr)^2equiv 4pmod{11}$$ At this point, we again consider the squares modulo $11,$ as we did in the previous approach, to see that $n+(-4)equiv2pmod{11}$ and $n+(-4)equiv9pmod{11}$ are the only possibilities, meaning that $nequiv 6pmod{11}$ or $nequiv 2pmod{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 $xequiv81pmod{143}$ or $xequiv29pmod{143},$ as desired.

From $xequiv 3mod 13$ we conclude that $$x^2equiv 9mod 13$$define $y=x^2$, therefore $$2y+5equiv 4mod 11\yequiv 9mod 13$$applying Chinese Remainder Theorem on the above set of equations we conclude that $$yequiv126mod 143$$therefore $$x^2equiv 126mod 143$$among which the answers with $xequiv 3mod 13$ are acceptable. Now let $$x=143k+rquad,quad 0le r<143$$by substitution we obtain $$x^2equiv r^2equiv 126 mod 143$$Numerical simulations show that the only possible values for $r$ are $$29quad 62quad 81quad 114$$also the constraint $xequiv 3mod 13$ imposes that $$requiv 3 mod 13$$ which leaves us with $$r=29\r=81$$therefore we if an answer $x$ exists, it must be either$$xequiv 29mod 143$$or $$xequiv 81mod 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+1equiv 2times29^2+1equiv 2times (-4)^2+1equiv 33equiv 0mod 11$$also for $x=143k+81$ we have $$2x^2+1equiv 2times81^2+1equiv 2times (-7)^2+1equiv 99equiv 0mod 11$$

Conclusion

The only answers are$$xequiv 29text{ or }81mod 143$$

HINT:

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