Recall the fact that all primes of the form -save from the number 2- are fermat primes -and conversly- (* that is easy to show, if you have not seen it, ask)

Okay, first remember that there are primitive roots ( or generators) in

And there are non-quadratic residues.

So we'd like to show that occurs in our case. -remember that the set of generators is included in the set of non-quadratic residues, see here-

We can write: with such that - since p>2, the case p=2 is trivial-

Then: equality occurs iff

Hence if is not of the form (that is ) there's always a non-quadratic residue that is not a generator.

But, if p is of the form , then all non-quadratic residues are also generators.