Better method to solve $x^2-x-1=0$ modulo $11$ 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?
 A: 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.)
A: 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: 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$.
A: 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.$$
A: 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.
