Cryptography Reference
In-Depth Information
φ(
)
of order
in this group. But it may also happen that there are no primitive roots
modulo
n
. For example:
n
Exercise 2.26
Prove that there are no primitive roots modulo 12 by showing that
the three nonidentity elements of
Z
12
have order 2.
8 is the smallest value for which there are no primitive roots, for it
can be shown that an integer
n
has a primitive root if and only if
n
In fact,
n
=
p
t
2
p
t
,
=
2
,
4
,
,
where
p
is an odd prime. The existence of primitive roots when
n
p
is prime will
be proved in Corollary 2.6 as a consequence of a more general result about finite
fields. Based on this result, we are going to show that, in fact, there are primitive
roots modulo any odd prime power. We start by dealing with a squared prime, and
we leave the proof of this case as an exercise:
=
Z
p
2
is cyclic, i.e., there exists
a primitive root modulo
p
2
.(Hint:Let
g
be a primitive root modulo
p
. Then
g
Exercise 2.27
Show that, if
p
is an odd prime, then
p
is also a primitive root modulo
p
and, if
g
is not a primitive root modulo
p
2
, i.e., if
g
p
−
1
+
mod
p
2
p
−
1
mod
p
2
≡
1
(
)
, then
(
g
+
p
)
≡
1
(
)
, so that
g
+
p
is a primitive
root modulo
p
2
.)
Next we show that, for any odd prime
p
, there exists a primitive root modulo
p
t
for each positive integer
t
.
Z
p
t
is a cyclic
Theorem 2.19
Let p be an odd prime and t a positive integer. Then
group.
Proof
By the preceding exercise we know that the result is true for
t
=
2 and that,
in fact, there exists a generator
g
of
Z
p
2
such that
g
mod
p
is also a generator of
Z
p
.
∈ Z
p
t
is a generator for all
t
We claim that
g
≥
2. Since
g
is a generator of
Z
p
2
,we
and we will now show that
g
p
t
−
2
know that
g
p
−
1
mod
p
2
(
p
−
1
)
≡
mod
p
t
≡
(
)
(
)
1
1
.
We know that this is true for
t
=
2 and, by induction, we assume that
t
≥
3 and that
g
p
t
−
3
(
p
−
1
)
≡
mod
p
t
−
1
1
(
).
Since
p
does not divide
g
,
p
t
−
2
does not divide
g
either and so, by Euler's theorem
we have that
g
p
t
−
3
g
φ(
p
t
−
2
(
p
−
1
)
≡
)
≡
mod
p
t
−
2
1
(
).
such that
g
p
t
−
3
rp
t
−
2
, where
p
does not divide
r
because of the induction hypothesis. Now, we raise the terms of this equality to
the
p
th power and, using the binomial expansion for
g
p
t
−
2
(
p
−
1
)
=
∈ Z
+
Thus there exists
r
1
(
p
−
)
=
(
rp
t
−
2
1
p
,we
1
+
)
obtain:
p
2
(
g
p
t
−
2
(
p
−
1
)
=
pr p
t
−
2
rp
t
−
2
2
rp
t
−
2
p
rp
t
−
1
mod
p
t
1
+
+
)
+···+
(
)
≡
1
+
(
).
