Solve quadratic congruence $x^2\equiv 51x+ 43 \pmod {\!187 =11\cdot 17 }$

$\begingroup$

Given $x^2 - \overline{51}x - \overline{43} = \overline{0}$.

Solve it in $\mathbb{Z}/187\mathbb{Z}$.

First of all, does the $\overline{x}$ mean that $\overline x = \{x + z \ | z\in I\}$?

I am getting really confused, because 187 is composite. I think I should somehow decompose this equation into two equations and solve them in $\mathbb{Z}/11\mathbb{Z}$ and $\mathbb{Z}/17\mathbb{Z}$, but I'm not sure.

And what is the pattern to solve things like that?

$\endgroup$ 1

2 Answers

$\begingroup$

Yes, find the roots $\,r_1,r_2\,$ mod $17,\,$ and the roots $\,s_1,s_2\,$ mod $11$. Then by CRT (see Remark below) each of the four pairs $\,(r_i,s_j)\,$ corresponds to a unique root mod $\,17\cdot 11.\,$

It is easiest to solve the CRT system generically. Suppose $\,x\equiv r\pmod{17}\,$ and $\,x\equiv s\pmod{11}.\,$ Then $\, x\equiv r\!+\!17j,\,$ so ${\rm mod}\ 11\!:\ s\equiv x\equiv r\!+\!17j\equiv r\!+\!6j\iff 6j\equiv s\!-\!r\iff \color{#c00}{j\equiv 2(s\!-\!r)}.\,$ Thus $\, x=r\!+\!17\color{#c00}j = r+17(\color{#c00}{2(s\!-\!r)}+11k) = \color{#0a0}{34s-33r} + 17\cdot11\,k$

Finally plug all four values of $\,r_i,s_j\,$ into $\, \color{#0a0}{34s-33r}\,$ to get all four solutions mod $\,17\cdot11$.

You'll end up discovering $\ \ \bbox[8px,border:2px solid blue]{ f(x) \equiv (x\!-\!3)(x\!-\!48)\equiv (x\!-\!14)(x\!-\!37) \ \ \pmod{187}}$

Remark $\ $ If $\,m,n\,$ are coprime then, by CRT, solving a polynomial $\,f(x)\equiv 0\pmod{mn}\,$ is equivalent to solving $\,f(x)\equiv 0\,$ mod $\,m\,$ and mod $\,n.\,$ By CRT, each combination of a root $\,r_i\bmod m\,$ and a root $\,s_j\bmod n\,$ corresponds to a unique root $\,t_{ij}\bmod mn,\,$ i.e.

$$\begin{eqnarray} f(x)\equiv 0\pmod{mn}&\overset{\rm CRT}\iff& \begin{array}{}f(x)\equiv 0\pmod m\\f(x)\equiv 0\pmod n\end{array} \\ &\iff& \begin{array}{}x\equiv r_1,\ldots,r_k\pmod m\phantom{I^{I^{I^I}}}\\x\equiv s_1,\ldots,s_\ell\pmod n\end{array}\\ &\iff& \left\{ \begin{array}{}x\equiv r_i\pmod m\\x\equiv s_j\pmod n\end{array} \right\}_{\begin{array}{}1\le i\le k\\ 1\le j\le\ell\end{array}}^{\phantom{I^{I^{I^I}}}}\\ &\overset{\rm CRT}\iff& \left\{ x\equiv t_{i j}\!\!\pmod{mn} \right\}_{\begin{array}{}1\le i\le k\\ 1\le j\le\ell\end{array}}\\ \end{eqnarray}\qquad\qquad$$

$\endgroup$ $\begingroup$

HINT.-$x^2-51x-43=0$ modulo $187=11\cdot17$ You have $$\begin{cases}x^2+4x+1=(x-3)(x-4)=0 \text{ in } \Bbb F_{11}\\x^2+8=(x-3)(x-14)=0 \text{ in } \Bbb F_{17}\end{cases}$$ Try now to apply chinese theorem.

$\endgroup$ 1

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy