1
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ Thanks for your help! Is there a clever way to argument why your solution gives me all possible solutions $\pmod{143}$? $\endgroup$ – Johny Dow Jan 6 '19 at 10:10
  • 1
    $\begingroup$ 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. $\endgroup$ – Cameron Buie Jan 6 '19 at 15:36
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks! Am I right that only trial and error leads to the values of r? $\endgroup$ – Johny Dow Jan 5 '19 at 21:40
  • 1
    $\begingroup$ 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$ $\endgroup$ – Mostafa Ayaz Jan 5 '19 at 21:45
  • 1
    $\begingroup$ @Johny Mostafa is correct. That's why it's better to deal with the squares at a smaller modulus, instead. $\endgroup$ – Cameron Buie Jan 5 '19 at 23:08
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Johny Dow Jan 5 '19 at 21:45

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.