4
$\begingroup$

I want to solve $x^2-x-1=0$ modulo $11$. I already know that the solutions are $x=4$ modulo $11$ and $x=8$ modulo $11$, but I got this result by trying. I also know that I can get these solutions by using the usual quadratic formula and doing some congruences as follows: $$x=\frac{1\pm \sqrt{5}}{2}\equiv_{11}\frac{1\pm \sqrt{16}}{2}\equiv_{11}\frac{1\pm 4}{2}$$ $$x_+\equiv_{11}\frac{1+ 4}{2}\equiv_{11}\frac{5}{2}\equiv_{11}\frac{16}{2}=8$$ $$x_-\equiv_{11}\frac{1- 4}{2}\equiv_{11}\frac{-3}{2}\equiv_{11}\frac{8}{2}=4$$ However, in this method I have to sum $11$ to some numbers until I get one that is in $\mathbb{F}_{11}$. What if I keep summing and summing and I don't get one in $\mathbb{F}_{11}$? When can I conclude that the equation has no solution? Is there a better method to do this?

$\endgroup$
6
  • 2
    $\begingroup$ It boils down to whether $\sqrt 5$ exists or not modulo $11$, as you can see. There is a concept, the Legendre symbol of $5$ modulo $11$, that will tell you whether there is an element $x$ such that $x^2 \equiv 5 \pmod{11}$ or not. Once you confirm that the Legendre symbol is $1$, you can then add multiples of $11$ until you succeed, but you know that you will succeed eventually. On the other hand, if the Legendre symbol is $-1$, then $\sqrt 5$ doesn't exist modulo $11$ and therefore you can conclude that there is no solution of the system. $\endgroup$ Oct 26, 2021 at 16:11
  • 1
    $\begingroup$ Evaluating the Legendre symbol uses some standard rules : you have some additive and multiplicative properties and you have a "quadratic reciprocity law". This law will tell you, in our case, that $x^2 \equiv 5 \pmod{11}$ has a solution if and only if $x^2 \equiv 11 \pmod{5}$ has a solution, but the latter equation is clearly solvable since $x^2 \equiv 1 \pmod{5}$ has solutions $1,-1$. Thus, you can "add $11$" till you get a square, but also be reassured that such a square will occur. It so happens that $5+11$ works. $\endgroup$ Oct 26, 2021 at 16:14
  • $\begingroup$ We have $$(2x-1)^2-5=4(x^2-x-1)$$ So, you have to solve $y^2\equiv 5\mod 11$, which is equivalent to $y^2\equiv 16\mod 11$. Now, the solutions can be seen immediately. $\endgroup$
    – Peter
    Oct 26, 2021 at 16:16
  • $\begingroup$ For the slightly more general problem of finding a square root mod a prime, see e.g. Tonelli-Shanks algorithm $\endgroup$ Oct 26, 2021 at 16:19
  • 1
    $\begingroup$ @TeresaLisbon I hadn't thought about using the Legendre symbol here. Thank you very much, this was really helpful $\endgroup$
    – kubo
    Oct 26, 2021 at 16:53

5 Answers 5

3
$\begingroup$

At the point we reach $\sqrt{5}$, we are looking for whether there is an integer solution to $x^2\equiv_{11} 5$. If there is, then there is some solution where $x\in \{0,\dots,10\}$, because $(x-11)^2\equiv_{11} x^2+11(-2x)+11\times 11 \equiv_{11} x^2$, so we could continue subtracting $11$ from $x$ (or adding $11$) until $x$ is in the right range.

Thus, you have to try each possibility between $0$ and $10$: or, using the "add $11$ to $5$ until reaching a square number" reframing of this calculation, you have to repeat the process $10$ times (until reaching $5+11\times 10=115$) to establish that no solution exists. (Though of course, in this case two solutions do exist.)

$\endgroup$
3
$\begingroup$

Multiply by $4$ and complete the square:

$$\begin{align} x^2-x-1\equiv0 &\iff4x^2-4x-4\equiv0\\ &\iff(2x-1)^2-5\equiv0\\ &\iff(2x-1)^2\equiv5\equiv16=(\pm4)^2 \end{align}$$

so

$$2x\equiv \begin{cases} +4+1=5\equiv16\\ -4+1=-3\equiv8 \end{cases} $$

hence $x\equiv8$ and $4$.

The key here is that $5$ is a quadratic residue mod $11$. It's possible to know which numbers are quadratic residues (and which ones aren't) without necessarily knowing their "square roots," but for small primes like $11$ it's as quick to run through the possibilities as it is to apply any fancy theory.

$\endgroup$
2
$\begingroup$

A quadratic equation modulo an odd prime $p$ will have a solution if and only if its discriminant is a square modulo $p$. That's analogous to what you know about real quadratics.

In general, half the nonzero residues modulo $p$ will be squares, half not. Deciding which is an important question in elementary number theory. Until you learn about quadratic reciprocity you should use trial and error. Since $(-x)^2 = x^2$ you need only try squaring $1, 2, \ldots, (p-1)/2$.

$\endgroup$
1
$\begingroup$

Let us subtract $11$ and realize that $$x^2-x-12=(x-4)(x+3).$$ The solutions are $4$ and $-3,$ modulo $11$ they are $$4 \quad \text{and} \quad 8.$$

$\endgroup$
1
$\begingroup$

If the problem is finding a square root of $5\bmod 11$, this can be done using what I call the "root-to-power method".

Since $11-1$ is divisible by $2$ but not by $4$, any quadratic residue $r$ will have a square root that is also a power of $r\bmod 11$. The square root can then be calculated as a power, which requires $O(\log n)$ multiplications where $n$ is the exponent.

To wit, if $r$ is a nonzero quadratic residue $\bmod 11$, then $r^5\equiv1$ and thus $r^6\equiv r$. Then the candidate square roots of $r$ would be square roots of $r^6$, thus $\pm r^3$.

With $r\equiv5$ the indicated multiplication leads to $\pm4$, which can be checked by directly calculating $(\pm4)^2\equiv5$. (Had this failed, the square root and thus the quadratic equation would have had no solution.) So we can confidently put in those values for the square roots of $5$ with bounded trial and error, and proceed from there.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .