Theorem: Let p be an odd prime the number of quadradic residues (modulo classes) is the same as the number of quadradic non-residues.
Proof: I can write the prove, but I am sure you learned this theorem.
Consider our incongruents integers:
The idea is that since the number of quadradic residues is equal to non-residues they MUST be next to each other unless they alternate:
residue, non-residue, ...
(Sine 1 is residue).
But that cannot happen.
See if you can finish it.