1
$\begingroup$

How to find solutions for:

  • $x^2\equiv 8\pmod{ 3}$
  • $x^2\equiv 15\pmod{ 31}$
  • $x^2\equiv 54\pmod{ 7}$
  • $x^2\equiv625\pmod{9973}$
$\endgroup$
2
  • 1
    $\begingroup$ Make the list.. mmh, nah $\endgroup$ Jan 10, 2016 at 12:11
  • $\begingroup$ Quadratic reciprocity $\endgroup$
    – vonbrand
    Jan 10, 2016 at 23:22

2 Answers 2

1
$\begingroup$

The first and third are easy, you just check the $3$ and $7$ cases respectively (you can get away with $1$ and $3$ cases respectively if you're a bit clever). The fourth you can solve by taking the square root. And lastly, the second one, you may look for perfect squares among all the numbers $n\equiv 15 \pmod{31}$. It shouldn't take long.

$\endgroup$
1
$\begingroup$

HINT: First use Euler's criterion to make sure that they have solutions. Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely,

Let $p$ be an odd prime and $a$ an integer coprime to $p$. Then

$a^{\tfrac{p-1}{2}} \equiv \begin{cases} \;\;\,1\pmod{p}& \text{ if there is an integer }x \text{ such that }a\equiv x^2 \pmod{p}\\ -1\pmod{p}& \text{ if there is no such integer.} \end{cases}$

Then use Quadratic reciprocity to find those solutions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.