I think the proof would be a lot easier if you was an odd prime. Anyway, if is a primitive root then,

Contains all the elements of

But since is a quadradic residue.

That means is a quadradic residue.

Then all numbers are quadradic residues of , which is surly not possible unless .

Note: By odd primes the proof is extremely simple if is a quadradic residue then,

But that is not possible because the order of is .