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

From Number

(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

## Contents

## 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:

- If , is a primitive root modulo .
- If , then , and is a primitive root modulo .
- If , then , and is a primitive root modulo .

## 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

- Quadratic nonresidue that is not minus one is primitive root for safe prime
- Congruence condition for minus one to be a quadratic residue
- 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.