2
$\begingroup$

Which primes divide $x^2-5$?

What I have tried:

If $p$ divides $x^2 -5 $ then: $$x^2= 5\pmod{p}$$ Therefore, from Euler's extended theorem we get that for primes s.t $\gcd(5,p)=1$ (which are all except $5$ which can be checked manually), we have: $$5^{(p-1)/2}=1\pmod{p}$$ These are the primes that $5$ is not a primitive root modulo for.

How can I carry on from here? Are there any other ways to solve this neatly?

Thanks!

$\endgroup$
  • 1
    $\begingroup$ Do you know quadratic reciprocity? $\endgroup$ – Wojowu Jan 23 at 17:35
  • $\begingroup$ @Wojowu yes in the basic case $\endgroup$ – Mickey Jan 23 at 17:36
  • $\begingroup$ What do you mean with "the basic case"? $\endgroup$ – Wojowu Jan 23 at 17:39
  • $\begingroup$ @Wojowu the basic theorem that appears in the wikipedia link, and the "commutative" rule used in the answer below (which is part of that theorem) $\endgroup$ – Mickey Jan 23 at 17:52
3
$\begingroup$

By quadratic reciprocity, and since $5\equiv 1\pmod 4$, $5$ is a square mod $p$ (an odd prime) iff $p$ is a square mod $5$, that is, if $p$ is $0$, $1$ or $4$ mod $5$, or more visually, if $p=5$ or the last digit of $p$ is $1$ or $9$.

Of course, $2$ can also divide $x^2-5$, namely when $x$ is odd.

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