4
$\begingroup$

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 1

5
$\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
  • $\begingroup$ yes I do thatnk you very much $\endgroup$
    – Pasie15
    Commented Dec 2, 2014 at 2:25
  • $\begingroup$ @Pasie15 I've written an answer on quadratic formula for congruences. $\endgroup$
    – user26486
    Commented May 5, 2015 at 3:19

You must log in to answer this question.

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