Quadratic residue modulo p Reading a book, I've come to a point where the author is trying to determine for which odd primes p is 5 a quadratic residue modulo p. How do you come to the conclusion that p has to be congruent with 1 modulo 5 or with 4 modulo 5?
Thanks.
 A: We may avoid invoking the quadratic reciprocity theorem by exploiting a bit of field theory.
Given some prime $p>5$, the splitting field of the polynomial $\Phi_5(x)=x^4+x^3+x^2+x+1$ over $\mathbb{F}_p$ is given by $\mathbb{F}_{p^k}$, where $k$ is the least positive integer ensuring $5\mid(p^k-1)$. 
If $p\equiv 1\pmod{5}$ we have that $k=1$, hence $\Phi_5(x)$ has a root $\alpha\in\mathbb{F}_p$ and 
$$\left(\alpha+\frac{1}{\alpha}\right)^2+\left(\alpha+\frac{1}{\alpha}\right)-1\equiv 0\pmod{p} $$
holds, implying that $\left(2\alpha+1+\frac{2}{\alpha}\right)^2\equiv5\pmod{p}$, so $\left(\frac{5}{p}\right)=1$.
If $p\equiv 4\pmod{5}$ we have that $k=2$, hence $\Phi_5(x)$ factors over $\mathbb{F}_p$ as the product of two quadratic polynomials, since $\Phi_5(x)$ has no root in $\mathbb{F}_p$ (there are no order-$5$ elements of $\mathbb{F}_p^*$ by Lagrange's theorem). So we have
$$ \Phi_5(x)= (x^2+ax+b)(x^2+(1-a)x+b^{-1}) $$
for some $a,b\in\mathbb{F}_p$, and the constraints $a+b-a^2+b^{-1}\equiv 1\equiv b-ab+ab^{-1}\pmod{p}$ given by the coefficients of $x$ and $x^2$ still imply that $5$ is a quadratic residue $\pmod{p}$.
If $p\equiv 2,3\pmod{5}$ both the polynomials $\Phi_5(x)$ and $x^2+x-1$ are irreducible $\!\!\pmod{p}$.
This immediately implies that $\left(\frac{5}{p}\right)=-1$.
Summarizing, for any prime $p>5$ we have that $5$ is a quadratic residue iff $p\equiv\pm 1\pmod{5}$.
A: Quadratic reciprocity.  The (nonzero) quadratic residues mod $5$ are $1$ and $4$ ($1^2 \equiv 4^2 \equiv 1 \mod 5$ and $2^2 \equiv 3^2 \equiv 4 \mod 5$).
Since $(5-1)/2$ is even, $5$ is a quadratic residue mod odd prime $p$ if and only if $p$ is a quadratic residue mod $5$.
