Existence of Primitive Roots
Recall from Section 2.1.2 that the order of an
element
in a finite group is the smallest
such that
. In this section, we prove that
is cyclic by
using the results of Section 2.5.1 to produce an element
of
of order
for each prime power divisor
of
, and then we multiply these together to obtain an element of
order
.
We will use the following lemma to assemble elements of
each order dividing
to produce an
element of order
.
Lemma 2.5
Suppose
have orders
and
, respectively,
and that
. Then
has order
.
Proof.
This is a general fact about commuting elements of any group; our proof
only uses that
![$ ab=ba$](img401.png)
and nothing special about
![$ (\mathbb{Z}/n\mathbb{Z}{})^*$](img477.png)
. Since
the order of
![$ ab$](img826.png)
is a divisor of
![$ rs$](img827.png)
.
Write this divisor as
![$ r_1 s_1$](img829.png)
where
![$ r_1\mid r$](img830.png)
and
![$ s_1\mid s$](img831.png)
.
Raise both sides of the equation
to the power
![$ r_2 = r/r_1$](img833.png)
to obtain
Since
![$ a^{r_1 r_2 s_1} = (a^{r_1 r_2})^{s_1} = 1$](img835.png)
, we have
so
![$ s\mid r_1 r_2 s_1$](img837.png)
.
Since
![$ \gcd(s,r_1 r_2)=\gcd(s,r) = 1$](img838.png)
, it follows that
![$ s=s_1$](img839.png)
.
Similarly
![$ r=r_1$](img840.png)
, so the order of
![$ ab$](img826.png)
is
![$ rs$](img827.png)
.
Theorem 2.5 (Primitive Roots)
There is a primitive root modulo any prime
. In particular,
the group
is cyclic.
Proof.
The theorem is true if
![$ p=2$](img517.png)
, since
![$ 1$](img49.png)
is a primitive root, so we may assume
![$ p>2$](img518.png)
.
Write
![$ p-1$](img531.png)
as a product of distinct prime powers
![$ q_i^{n_i}$](img841.png)
:
By Proposition
2.5.5,
the polynomial
![$ x^{q_i^{n_i}}-1$](img843.png)
has exactly
![$ q_i^{n_i}$](img841.png)
roots, and the polynomial
![$ x^{q_i^{n_i-1}}-1$](img844.png)
has exactly
![$ q_i^{n_i-1}$](img845.png)
roots.
There are
![$ q_i^{n_i} - q_i^{n_i-1}=q_i^{n_i-1}(q_i-1)$](img846.png)
elements
![$ a\in\mathbb{Z}/p\mathbb{Z}{}$](img847.png)
such
that
![$ a^{q_i^{n_i}}=1$](img848.png)
but
![$ a^{q_i^{n_i-1}}\neq 1$](img849.png)
;
each of these elements has order
![$ q_i^{n_i}$](img841.png)
.
Thus for each
![$ i=1,\ldots, r$](img850.png)
, we can choose an
![$ a_i$](img851.png)
of order
![$ q_i^{n_i}$](img841.png)
.
Then, using Lemma
2.5.7 repeatedly, we see that
has order
![$ q_1^{n_1}\cdots q_r^{n_r} = p-1$](img853.png)
,
so
![$ a$](img37.png)
is a primitive root modulo
![$ p$](img14.png)
.
Example 2.5
We illustrate the proof of Theorem
2.5.8 when
![$ p=13$](img854.png)
. We have
The polynomial
![$ x^4 - 1$](img856.png)
has roots
![$ \{1,5,8,12\}$](img857.png)
and
![$ x^2-1$](img786.png)
has roots
![$ \{1,12\}$](img858.png)
, so we may take
![$ a_1=5$](img859.png)
.
The polynomial
![$ x^3-1$](img860.png)
has roots
![$ \{1,3,9\}$](img861.png)
, and we set
![$ a_2=3$](img862.png)
.
Then
![$ a=5\cdot 3=15\equiv 2$](img863.png)
is a primitive root.
To verify this, note that
the successive powers of
![$ 2\pmod{13}$](img864.png)
are
Example 2.5
Theorem
2.5.8 is false if, e.g.,
![$ p$](img14.png)
is replaced by a
power of
![$ 2$](img251.png)
bigger than
![$ 4$](img382.png)
. For example, the four elements of
![$ (\mathbb{Z}/8\mathbb{Z}{})^*$](img866.png)
each have order dividing
![$ 2$](img251.png)
, but
![$ \varphi (8)=4$](img867.png)
.
Theorem 2.5 (Primitive Roots mod
![$ p^n$](img613.png)
)
Let
be a power of an odd prime. Then there
is a primitive root modulo
.
The proof is left as Exercise 2.28.
Proof.
The primitive roots modulo
![$ n$](img7.png)
are the generators of
![$ (\mathbb{Z}/n\mathbb{Z}{})^*$](img477.png)
, which by assumption is cyclic of order
![$ \varphi (n)$](img13.png)
.
Thus they are in bijection with the generators of any cyclic group
of order
![$ \varphi (n)$](img13.png)
. In particular, the number of primitive roots
modulo
![$ n$](img7.png)
is the same as the number of elements of
![$ \mathbb{Z}/\varphi (n)\mathbb{Z}{}$](img869.png)
with additive order
![$ \varphi (n)$](img13.png)
. An element of
![$ \mathbb{Z}/\varphi (n)\mathbb{Z}{}$](img869.png)
has additive
order
![$ \varphi (n)$](img13.png)
if and only if it is coprime to
![$ \varphi (n)$](img13.png)
. There
are
![$ \varphi (\varphi (n))$](img868.png)
such elements, as claimed.
Example 2.5
For example, there are
![$ \varphi (\varphi (17)) = \varphi (16)=2^4-2^3=8$](img870.png)
primitive roots mod
![$ 17$](img133.png)
, namely
![$ 3, 5, 6, 7, 10, 11, 12, 14$](img871.png)
. The
![$ \varphi (\varphi (9)) = \varphi (6) = 2$](img872.png)
primitive roots modulo
![$ 9$](img873.png)
are
![$ 2$](img251.png)
and
![$ 5$](img17.png)
. There are no primitive roots modulo
![$ 8$](img874.png)
, even though
![$ \varphi (\varphi (8)) = \varphi (4) = 2>0$](img875.png)
.
William
2007-06-01