Does the congruence $x^2 - 3x - 1 \equiv 0$ (mod 31957) have any solutions? (A hint given is that I can use the quadratic formula to find out what number you need to take the square root of modulo the prime 31957)
This a number theory problem I cant understand. Any help? I would to see an example of a solution to this. Thank you.
$\endgroup$1 Answer
$\begingroup$It's true, you can use the quadratic formula in this context. You obtain:
$x \equiv 2^{-1}(3\pm\sqrt{9+4}) \equiv 15979(3\pm\sqrt{13}) \pmod{31957}$
Note that the multiplicative inverse of $2$ is the number whose product with $2$ is congruent to $1$, modulo $31957$. This is going to work if and only if $13$ is a perfect square modulo $31957$.
This is generally done by evaluating the Legendre symbol $\left(\frac{13}{31957}\right)$ Do you know how to do that? (Note that $31957$ is prime and congruent to $1$ modulo $4$.)
$\endgroup$ 2
