Let

*p* be an odd prime and

*r* be a primitive root of

*p*.

a) Prove that the Legendre symbol (r/p) = -1 and conclude that

is a nonquadratic residue for every odd positive integer k.

If then . Get now a contradiction rising to the power both sides .

The second part follows at once

Tonio
b) Prove that if every nonquadratic residue of

*p* is a primitive root of

*p*, then

*p* is a Fermat prime. (Hint: Part (a) should be helpful)

c) Prove that if

*p* is a Fermat prime, then ever nonquadratic residue modulo p is a primitive root of

*p*.