First, we recall a well-known fact: exactly half of the linear residues mod except zero are quadratic residues mod . Now, by Fermat's little theorem, we have
If is a quadratic residue mod then for some . Then we must have from Fermat's little theorem.
So it suffices to prove that for quadratic nonresidues we have Consider the equation in It has at most roots. But we've already shown that all the quadratic residues there's of them mod are roots of this equation. So there's no other root, meaning for any quadratic nonresidue we can't have . But , so it must be the case that for quadratic nonresidues we have .
Hence we always have