# Proof involving primes of the form $5k+1$ and $5k+4$

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!

-
If $x$ is an integer and $x^2 \equiv a \pmod 5,$ what can you tell me about $a?$ –  Will Jagy Dec 11 '12 at 2:47
Do you know quadratic reciprocity? –  Thomas Andrews Dec 11 '12 at 2:53

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

-
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$. –  Thomas Andrews Dec 11 '12 at 12:34
@ThomasAndrews, thanks for your observation. Type error rectified. –  lab bhattacharjee Dec 11 '12 at 14:48
You are wrong about the fourth power of $5k\pm 1$ there. $4$ is definitely a square mod 5, but not that way... –  Thomas Andrews Dec 11 '12 at 15:17
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. –  TMM Dec 11 '12 at 15:48
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. –  TMM Dec 11 '12 at 15:59