Show that if p is not a Fermat prime, then there is a such that
and [a]_p is not a generator of .
Here
is legendre symbol.
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.