View source for Safe prime has plus or minus two as a primitive root

==Statement==

Suppose <math>p</math> is a [[fact about::safe prime]], i.e., <math>p</math> is an odd prime such that <math>(p-1)/2</math> is also prime (this is equivalent to saying that <math>(p-1)/2</math> is a [[fact about::Sophie Germain prime]]).

Then:

* If <math>p = 5</math>, <math>2</math> is a primitive root modulo <math>p</math>.
* If <math>(p-1)/2 \equiv 1 \pmod 4</math>, then <math>p \equiv 3 \pmod 8</math>, and <math>2</math> is a [[fact about::primitive root]] modulo <math>p</math>.
* If <math>(p-1)/2 \equiv 3 \pmod 4</math>, then <math>p \equiv 7 \pmod 8</math>, and <math>-2</math> is a [[fact about::primitive root]] modulo <math>p</math>.

==Related facts==

* [[Quadratic nonresidue equals primitive root for Fermat prime]]
* [[Quadratic nonresidue that is not minus one is primitive root for safe prime]]

==Facts used==

# [[uses::Quadratic nonresidue that is not minus one is primitive root for safe prime]]
# [[uses::Congruence condition for minus one to be a quadratic residue]]
# [[uses::Congruence condition for two to be a quadratic residue]]: For an odd prime <math>p</math>, <math>2</math> is a quadratic residue modulo <math>p</math> iff <math>p \equiv \pm 1 \pmod 8</math>, and a nonresidue iff <math>p \equiv \pm 3 \pmod 8</math>.

==Proof==

'''Given''': A safe prime <math>p</math>.

'''To prove''': If <math>p = 5</math> or <math>(p-1)/2 \equiv 1 \pmod 4</math>, then <math>2</math> is a primitive root modulo <math>p</math>. If <math>(p-1)/2 \equiv 3 \pmod 4</math>, then <math>-2</math> is a primitive root modulo <math>p</math>.

'''Proof''': Since <math>p > 3</math>, neither <math>2</math> nor <math>-2</math> is congruent to <math>-1</math> modulo <math>p</math>. Thus, by fact (1), it suffices to show in either case that <math>2</math> (or <math>-2</math>) is a quadratic nonresidue modulo <math>p</math>.

The cases <math>p = 5</math> and <math>(p-1)/2 \equiv 1 \pmod 4</math> are settled by fact (3).

In the case <math>(p-1)/2 \equiv 3 \pmod 4</math>, <math>p \equiv -1 \pmod 8</math>. By facts (2) and (3), <math>2</math> is a quadratic residue modulo <math>p</math> and <math>-1</math> is a quadratic nonresidue modulo <math>p</math>. Thus, <math>-2</math> is a quadratic nonresidue modulo <math>p</math>, completing the proof.