How to prove ($\frac{n}{p} ) = -1$ if $n$ is a quadratic non-residue $\pmod p$

Question

We can derive from Fermat's little theorem that ${ n }^{ \frac{(p-1)}{2} }\equiv 1\pmod p$ if a is a quadratic residue. How to prove a congruent $-1$ if $n$ is a quadratic non-residue?

Answer 1

This is because $x^2 \equiv 1 \pmod{p}$ implies $x \equiv \pm 1 \pmod{p}$, and by Fermat's little theorem we have $\left(n^{(p-1)/2}\right)^2 \equiv 1 \pmod{p}$. So the quantity is either $1$ or $-1$.

But we already found $\frac{p-1}{2}$ solutions to $x^{(p-1)/2} \equiv 1 \pmod{p}$, because there are that many quadratic residues; by Lagrange's theorem, there are no more solutions (a polynomial of degree $d$ has at most $d$ roots), so the rest of the $x^{(p-1)/2}$ must be $-1$.

Answer 2

Assuming that $p$ is an odd prime, we have that $(\mathbb{Z}/p\mathbb{Z})^*$ is a cyclic group with $(p-1)$ elements and the map $L:g\mapsto g^{\frac{p-1}{2}}$ is a homomorphism whose range is exactly $\{-1,+1\}$. By assuming $\xi$ is a generator for $(\mathbb{Z}/p\mathbb{Z})^*$, it is pretty clear that every element of the form $\xi^{\text{even}}$ is a quadratic residue and every element of the form $\xi^{\text{odd}}$ is a quadratic non-residue. With such representation it is also pretty clear that $L$ maps the quadratic residues to $1$ and the non-quadratic residues to $-1$.