Difference between revisions of "Safe prime has plus or minus two as a primitive root"

From Number
Jump to: navigation, search
(Created page with '==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 sa...')
 
 
Line 8: Line 8:
 
* 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 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>.
 
* 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==
 
==Facts used==

Latest revision as of 15:18, 21 April 2009

Statement

Suppose is a safe prime, i.e., is an odd prime such that is also prime (this is equivalent to saying that is a Sophie Germain prime).

Then:

Related facts

Facts used

  1. Quadratic nonresidue that is not minus one is primitive root for safe prime
  2. Congruence condition for minus one to be a quadratic residue
  3. Congruence condition for two to be a quadratic residue: For an odd prime , is a quadratic residue modulo iff , and a nonresidue iff .

Proof

Given: A safe prime .

To prove: If or , then is a primitive root modulo . If , then is a primitive root modulo .

Proof: Since , neither nor is congruent to modulo . Thus, by fact (1), it suffices to show in either case that (or ) is a quadratic nonresidue modulo .

The cases and are settled by fact (3).

In the case , . By facts (2) and (3), is a quadratic residue modulo and is a quadratic nonresidue modulo . Thus, is a quadratic nonresidue modulo , completing the proof.