5
$\begingroup$

I am having trouble figuring out how to prove this:

If $p$ is a prime not equal to $2$ nor $5$, and $n$ is any integer, show that $p$ must be of the form $5k+1$ or $5k+4$ if $p \mid (n^2 - 5)$.

Any help is greatly appreciated!

  • 1
    If $x$ is an integer and $x^2 \equiv a \pmod 5,$ what can you tell me about $a?$2012-12-11
  • 1
    Do you know quadratic reciprocity?2012-12-11

1 Answers 1

3

Using Legendre Symbol and Quadratic Reciprocity Theorem,

$p\mid(n^2-5)\iff n^2\equiv5\pmod p\implies \left(\frac5p\right)=1$

$$\left(\frac p5\right)\left(\frac5p\right)=(-1)^{\frac{p-1}2\frac{5-1}2}=1$$ for odd prime $n$

So, $\left(\frac5p\right)=\left(\frac p5\right)$

Now, $(5k\pm1)^2\equiv1\pmod 5, (5k\pm2)^2\equiv4\pmod 5$

So, $\left(\frac p5\right)=1\iff p\equiv1,4\pmod 5$

  • 0
    Nowhere is it said that $n$ is odd, nore do we know what $\left(\frac{5}{n}\right)=1$. You've got $n$ confused with $p$.2012-12-11
  • 0
    @ThomasAndrews, thanks for your observation. Type error rectified.2012-12-11
  • 0
    You are wrong about the fourth power of $5k\pm 1$ there. $4$ is definitely a square mod 5, but not that way...2012-12-11
  • 0
    @ThomasAndrews, thanks again.2012-12-11
  • 1
    Using the notation ${a \choose b}$ is wrong and confusing. These are not binomial coefficients but Legendre symbols, which should have a line in the middle.2012-12-11
  • 0
    @TMM, would you please share the reference/symbol?2012-12-11
  • 1
    You can right-click Thomas' post to see the LaTeX-source, or just copy: `\left(\frac{a}{b}\right)` = $\left(\frac{a}{b}\right)$. Any proper reference to the Legendre-symbol will contain these lines in the middle.2012-12-11
  • 0
    @TMM, thanks a lot for your help.2012-12-11