View source for Quadratic nonresidue equals primitive root for Fermat prime

{{primitive root fact for special kind of prime}}

==Statement==

Let <math>n</math> be a nonnegative integer such that the [[fact about::Fermat number]] <math>F_n</math> is prime, i.e., is a [[Fermat prime]]. Then, if <math>a</math> is a [[fact about::quadratic nonresidue]] modulo <math>F_n</math>, then <math>a</math> is a [[fact about::primitive root]] modulo <math>F_n</math>.

==Related facts==

* [[Prime divisor of Fermat number is congruent to one modulo large power of two]]
* [[Quadratic nonresidue that is not minus one is primitive root for safe prime]]
* [[Safe prime has plus or minus two as a primitive root]]

==Facts used==

# [[uses::Euler's criterion]]

==Proof==

'''Given''': A Fermat prime <math>F_n</math>, a quadratic nonresidue <math>a</math> modulo <math>F_n</math>.

'''To prove''': <math>a</math> is a primitive root modulo <math>F_n</math>.

'''Proof''': We need to show that the order of <math>a</math> modulo <math>F_n</math> is <math>F_n - 1 = 2^{2^n}</math>.

By fact (1), if <math>a</math> is a quadratic nonresidue modulo <math>F_n</math>, <math>a^{(F_n - 1)/2} \equiv -1 \pmod F_n</math>. Thus, the order of <math>a</math> modulo <math>F_n</math> does not divide <math>(F_n - 1)/2 = 2^{2^n - 1}</math>. On the other hand, the order divides <math>F_n - 1</math>. Thus, the order of <math>a</math> modulo <math>F_n</math> equals <math>F_n - 1</math>, so <math>a</math> is a primitive root modulo <math>F_n</math>.