6
$\begingroup$

I started learning number theory, specifically polynomial congruences, and need help with the following exercise. Here it is:

Does the congruence $x^2-6x-13 \equiv 0 \pmod{127}$ has solutions?

I tried to follow the method for solving general quadratic congruence but I didn't get really far. Here's what I've done so far:

Since $(4, 127) = 1$, we may complete the square by multiplying by $4$ without having to change the modulus in order to get the following equivalent congruence

$$(2x-6)^2 \equiv 36 - 4(-13) \pmod{127} \iff (2x-6)^2 \equiv 88 \pmod{127}.$$

If I'm heading in the right direction then I don't know how to continue from here. I suspect there is another method for solving this problem since I didn't make use of the fact that $127$ is prime. Also, the problem doesn't require to actually find the solutions but only determine if there are solutions. Possibly we can avoid computations and make use of some theorem/lemma to find if the congruence has solutions or not.

$\endgroup$
  • 1
    $\begingroup$ The quadratic formula, $x = \frac{6\pm\sqrt{(-6)^2 - 4\cdot 1\cdot (-13)}}{2\cdot 1}$ still works, since $127$ is an odd prime. Note, however, that square root and dividing by $2$ has a different meaning from what it does for real numbers (or, it has the same meaning, but potentially a very different result). $\endgroup$ – Arthur Sep 19 '17 at 11:16
4
$\begingroup$

. To find solutions of $x^2 - 6x - 13 \equiv 0 \mod 127$, we must write $x^2-6x - 13$ as a square of a linear term, plus a constant. It's seen easily that $x^2 - 6x - 13 = (x-3)^2 - 22$. Hence, the congruence is equivalent to $(x-3)^2 \equiv 22 \mod 127$.

Now, we must check if $22$ is a quadratic residue mod $127$. For this, we can use the Legendre symbol, whose notation I will keep the same as the binomial, so do not get confused. $$ \binom{22}{127} = \color{green}{\binom{11}{127}}\color{red}{\binom{2}{127}} = \color{green}{-\binom{127}{11}} \times \color{red}1 $$ where the terms with same color on the LHS and RHS are equal. The green equality comes by quadratic reciprocity and the second comes by the fact that $\binom{2}{p}$ is well known by the remainders which $p$ leaves when divided by $8$.

Now, we can do: $$ -\binom{127}{11} = -\binom{6}{11} = -\color{green}{\binom{2}{11}}\color{red}{ \binom{3}{11}} = -\color{green}{(-1)}\color{red}{(1)} = 1 $$

Again, the colored terms on the LHS and RHS are equal because the quantities $\binom 2p$ and $\binom 3p$ are well known.

Since we have obtained that the Legendre symbol is $1$, this implies the existence of a solution, and therefore two.

The question, though, is how to compute them. I do not know of any method other than brute force, unfortunately. However, our reward for writing $(x-3)^2 \equiv 22 \mod 127$ is that we basically only need to look for squares of the form $127k + 22$ to find a solution, rather than having to substitute values of $x$ into the expression $x^2-6x-13$ each time.

A brute force : the series $127k + 22 $ goes like : $22,149,276,403,530,657,\color{blue}{784},...$

lo and behold, $784 = 28^2$, hence this gives $x = 31$. Now, note that the congruence actually has two solutions, one given by $127 - 28 = 99$. You can check that $9801 = 99^2 = 22 + 127 \times 77$.

Hence, we get two solutions of $x$, namely $x= 31,102$.

$\endgroup$
  • $\begingroup$ I can't thank you enough for this answer! I understood everything and it made me see the link that I was missing between quadratic polynomial/residues and Legendre symbol. $\endgroup$ – user347616 Sep 19 '17 at 12:07
  • 1
    $\begingroup$ But of course, you are welcome! I should mention, +1 for your question. $\endgroup$ – астон вілла олоф мэллбэрг Sep 19 '17 at 12:08
  • 2
    $\begingroup$ Since $127$ is one less than a multiple of $4$, you can get the square roots by "root-power conversion". Fermat's Little Theorem gives $22^{126}\equiv 1$, and with $22$ being a quadratic residue then $22^{63}\equiv 1$. So $22^{64}\equiv 22$ assuring that $22^{32}\equiv 99$ will be one square root. Try it! $\endgroup$ – Oscar Lanzi Sep 19 '17 at 12:26
  • 1
    $\begingroup$ That is a much,much better method than the one I have suggested. I thank you for this. $\endgroup$ – астон вілла олоф мэллбэрг Sep 19 '17 at 12:29
1
$\begingroup$

Using the Berlekamp Algorithm for factoring a polynomial over $\mathbb{F}_{127}$ we immediately obtain that $$ x^2-6x-13=(x+25)(x+96). $$ So we have two solutions.

$\endgroup$
1
$\begingroup$

I am a congruence beginner like you.

I did in this way

completed the square $(x-3)^2-9\equiv 13 \mod 127$

$(x-3)^2\equiv 22 \mod 127$

Now call $r$ is the number such that $r^2\equiv 22\mod 127$?

Like a "modular" square root

I found here a way to find the roots

As $127\equiv 3 \mod 4$ then we have $r= \pm 22^{\frac{128}{4}} \mod 127$

$22^{32} =2^{32}\cdot 11^{32}$

$2^7\equiv 1 \mod 127\to 2^{28}\equiv 1 \mod 127\to \color{red}{2^{32}\equiv 2^4\mod 127}$

$11^{32}=121^{16}$ as $121\equiv 6 \mod 127$ we have $121^{16}\equiv 6^{16} \mod 127$ and then $6^{16}\equiv 2^{16}\cdot 3^{16} \mod 127$

$2^k \mod 127$ for $k=0,1,2\ldots$ is cyclical and is $1,2,4,8,16,32,64$ then repeats (because $127=2^7-1$) therefore $2^{16}\equiv 4 \mod 127$

$3^{16}\equiv 81^4 \mod 127\to 3^{16}\equiv 71 \mod 127$

Finally $6^{16}\equiv 4\cdot 71 \mod 127\to 6^{16}\equiv 30 \mod 127$ and $\color{red}{11^{32}\equiv 6^{16}\equiv 30 \mod 127}$

Collecting the parts in red colour we get $22^{32}\equiv 2^4\cdot 30 \mod 127$ that is $22^{32}\equiv 99\mod 127$ and $-22^{32} \equiv 28 \mod 127$

Concluding the two solutions are $x-3\equiv 99 \mod 127\to x\equiv 102 \mod 127$ and $x-3\equiv 28 \mod 127 \to x\equiv 31 \mod 127$

Edit

My solution is all but elegant. Anyway is a solution provided by a beginner like you and I hope it is understandable

$\endgroup$
  • $\begingroup$ It took me a little time to go through your solution but I made it. Thank you for the effort, it is always enlightening to see different solutions to the same problem. (+1) $\endgroup$ – user347616 Sep 19 '17 at 14:59
  • $\begingroup$ To compute $22^{32} \bmod127$ just square five successive times. $\endgroup$ – Oscar Lanzi Sep 19 '17 at 22:33
  • $\begingroup$ @OscarLanzi Why $22^{32}\equiv 22^5 \mod 127$? $\endgroup$ – Raffaele Sep 20 '17 at 13:11
  • $\begingroup$ I did not say that. Square five successive times means $22^{2^5}$. $\endgroup$ – Oscar Lanzi Sep 20 '17 at 13:42
0
$\begingroup$

I think you can try $$x=31.$$ It is valid.

Finally we have $$x^2-6x-13\equiv(x-31)(x-102) \pmod{127}.$$

$\endgroup$
0
$\begingroup$

This equation has roots modulo $127$ if and only if the reduced discriminant $\Delta'=9+13$ is a square modulo $127$. We'll use the laws of quadratic reciprocity.

$$\biggl(\frac{22}{127}\biggr)=\biggl(\frac{2}{127}\biggr)\biggl(\frac{11}{127}\biggr)=\biggl(\frac{11}{127}\biggr)\quad\text{since }127\equiv -1\mod8\quad (2^{\mathit{nd}}\textit{supplementary law}). $$ Now we have \begin{align}\biggl(\frac{11}{127}\biggr)&=\biggl(\frac{127}{11}\biggr)\bigl(-1\bigr)^{\tfrac{10\cdot126}4}=-\biggl(\frac{6}{11}\biggr)=-\biggl(\frac{2}{11}\biggr)\biggl(\frac{3}{11}\biggr)\\[1ex] &=+\biggl(\frac{3}{11}\biggr)=\biggl(\frac{11}{3}\biggr)\bigl(-1\bigr)^{\tfrac{2\cdot10}4}=-\biggl(\frac{2}{3}\biggr)=+1. \end{align} Thus the equation has roots.

$\endgroup$

Your Answer

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