Safe prime has plus or minus two as a primitive root
From Number
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.