# Better method to solve $x^2-x-1=0$ modulo $11$ [duplicate]

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?

• 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. Oct 26, 2021 at 16:11
• 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. Oct 26, 2021 at 16:14
• 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. Oct 26, 2021 at 16:16
• For the slightly more general problem of finding a square root mod a prime, see e.g. Tonelli-Shanks algorithm Oct 26, 2021 at 16:19
• @TeresaLisbon I hadn't thought about using the Legendre symbol here. Thank you very much, this was really helpful
– kubo
Oct 26, 2021 at 16:53

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.)

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.

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

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

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.