Primitive Roots and Discrete Logarithms — $(\mathbb{Z}/p\mathbb{Z})^*$ as a Cyclic Group

We prove that (Z/pZ)* is cyclic for every prime p and that the number of primitive roots is phi(p-1). We introduce the discrete logarithm (index), determine the structure of (Z/p^k Z)*, and discuss the computational hardness of the discrete logarithm problem (DLP).

Folio Official

March 1, 2026

1 Definition of Primitive Roots

Definition 1 (Primitive root).

For a positive integer

n

, an integer

g

with

ord_{n} (g) = φ (n)

is called a primitive root modulo

n

. When such a

g

exists,

(Z / n Z)^{*}

is a cyclic group generated by

\overset{g}{ˉ}

2 Cyclicity of $(Z / p Z)^{*}$

Lemma 2.

A polynomial of degree

d

over a field

F

has at most

d

roots.

Proof.

By induction on

d

. The case

d = 0

is clear. For

d \geq 1

, if

a

is a root, then

f (x) = (x - a) g (x)

with

de g g = d - 1

, so

f

has at most

1 + (d - 1) = d

roots. □

Theorem 3.

For every prime

p

(Z / p Z)^{*}

is a cyclic group of order

p - 1

Proof.

The group

(Z / p Z)^{*}

is a finite abelian group of order

p - 1

. For each positive divisor

d

p - 1

, set

ψ (d) = ∣ {a \in (Z / p Z)^{*} ∣ ord (a) = d} ∣

. If an element

a

of order

d

exists, then

1, a, a^{2}, \dots, a^{d - 1}

are

d

roots of

x^{d} - 1 = 0

. Over a field, a degree-

d

polynomial has at most

d

roots, so these are the only elements whose order divides

d

. Among them, exactly

φ (d)

have order precisely

d

. Thus

ψ (d) \in {0, φ (d)}

for each

d ∣ (p - 1)

On the other hand,

\sum_{d ∣ (p - 1)} ψ (d) = p - 1 = \sum_{d ∣ (p - 1)} φ (d)

(the latter being a standard identity for the totient function). It follows that

ψ (d) = φ (d)

for every

d ∣ (p - 1)

. In particular,

ψ (p - 1) = φ (p - 1) \geq 1

, so elements of order

p - 1

exist. □

Corollary 4.

The number of primitive roots modulo

p

φ (p - 1)

3 The Index (Discrete Logarithm)

Definition 5 (Index).

Let

g

be a primitive root modulo

n

and

g cd (a, n) = 1

. The unique non-negative integer

k

with

0 \leq k < φ (n)

satisfying

g^{k} \equiv a (mod n)

is called the index (or discrete logarithm) of

a

with respect to

g

, and is written

ind_{g} (a)

Theorem 6 (Properties of the index).

For a primitive root

g

modulo

n

$ind_{g} (ab) \equiv ind_{g} (a) + ind_{g} (b) (mod φ (n))$ .
$ind_{g} (a^{k}) \equiv k \cdot ind_{g} (a) (mod φ (n))$ .
$ord_{n} (a) = φ (n) / g cd (ind_{g} (a), φ (n))$ .

Proof.

(1) From

g^{ind_{g} (a)} \equiv a

and

g^{ind_{g} (b)} \equiv b

, we get

g^{ind_{g} (a) + ind_{g} (b)} \equiv ab \equiv g^{ind_{g} (ab)} (mod n)

. Since

g

has order

φ (n)

, the exponents agree modulo

φ (n)

. (2) Follows by repeated application of (1). (3) The equation

a^{k} \equiv 1

is equivalent to

k \cdot ind_{g} (a) \equiv 0 (mod φ (n))

, and the smallest positive

k

satisfying this is

φ (n) / g cd (ind_{g} (a), φ (n))

. □

4 Structure of $(Z / p^{k} Z)^{*}$

Theorem 7.

For an odd prime

p

and a positive integer

k

(Z / p^{k} Z)^{*}

is a cyclic group of order

φ (p^{k}) = p^{k - 1} (p - 1)

. In particular, primitive roots exist modulo

p^{k}

Remark 8.

The case

p = 2

is different:

(Z /2 Z)^{*} ≅ {1}

(Z /4 Z)^{*} ≅ Z /2 Z

, and for

k \geq 3

(Z / 2^{k} Z)^{*} ≅ Z /2 Z \times Z / 2^{k - 2} Z

(which is not cyclic).

5 The Discrete Logarithm Problem

Definition 9 (Discrete logarithm problem (DLP)).

Let

g

be a primitive root modulo a prime

p

and let

h \in (Z / p Z)^{*}

. The problem of finding

x

such that

g^{x} \equiv h (mod p)

is called the discrete logarithm problem.

Remark 10.

The DLP is believed to be computationally hard and serves as the security foundation for the Diffie–Hellman key exchange and the ElGamal cryptosystem. The most efficient known classical algorithm is the number field sieve, which runs in time

exp (O ((lo g p)^{1/3} (lo g lo g p)^{2/3}))

. The baby-step giant-step method solves the DLP in

O (p)

time and serves as a general-purpose approach.

Number Theory Algebra Textbook Primitive Roots Discrete Logarithm

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Primitive Roots and Discrete Logarithms — $(\mathbb{Z}/p\mathbb{Z})^*$ as a Cyclic Group

Folio Official

March 1, 2026

1 Definition of Primitive Roots

Definition 1 (Primitive root).

For a positive integer

n

, an integer

g

with

ord_{n} (g) = φ (n)

is called a primitive root modulo

n

. When such a

g

exists,

(Z / n Z)^{*}

is a cyclic group generated by

\overset{g}{ˉ}

2 Cyclicity of $(Z / p Z)^{*}$

Lemma 2.

A polynomial of degree

d

over a field

F

has at most

d

roots.

Proof.

By induction on

d

. The case

d = 0

is clear. For

d \geq 1

, if

a

is a root, then

f (x) = (x - a) g (x)

with

de g g = d - 1

, so

f

has at most

1 + (d - 1) = d

roots. □

Theorem 3.

For every prime

p

(Z / p Z)^{*}

is a cyclic group of order

p - 1

Proof.

The group

(Z / p Z)^{*}

is a finite abelian group of order

p - 1

. For each positive divisor

d

p - 1

, set

ψ (d) = ∣ {a \in (Z / p Z)^{*} ∣ ord (a) = d} ∣

. If an element

a

of order

d

exists, then

1, a, a^{2}, \dots, a^{d - 1}

are

d

roots of

x^{d} - 1 = 0

. Over a field, a degree-

d

polynomial has at most

d

roots, so these are the only elements whose order divides

d

. Among them, exactly

φ (d)

have order precisely

d

. Thus

ψ (d) \in {0, φ (d)}

for each

d ∣ (p - 1)

On the other hand,

\sum_{d ∣ (p - 1)} ψ (d) = p - 1 = \sum_{d ∣ (p - 1)} φ (d)

(the latter being a standard identity for the totient function). It follows that

ψ (d) = φ (d)

for every

d ∣ (p - 1)

. In particular,

ψ (p - 1) = φ (p - 1) \geq 1

, so elements of order

p - 1

exist. □

Corollary 4.

The number of primitive roots modulo

p

φ (p - 1)

3 The Index (Discrete Logarithm)

Definition 5 (Index).

Let

g

be a primitive root modulo

n

and

g cd (a, n) = 1

. The unique non-negative integer

k

with

0 \leq k < φ (n)

satisfying

g^{k} \equiv a (mod n)

is called the index (or discrete logarithm) of

a

with respect to

g

, and is written

ind_{g} (a)

Theorem 6 (Properties of the index).

For a primitive root

g

modulo

n

$ind_{g} (ab) \equiv ind_{g} (a) + ind_{g} (b) (mod φ (n))$ .
$ind_{g} (a^{k}) \equiv k \cdot ind_{g} (a) (mod φ (n))$ .
$ord_{n} (a) = φ (n) / g cd (ind_{g} (a), φ (n))$ .

Proof.

(1) From

g^{ind_{g} (a)} \equiv a

and

g^{ind_{g} (b)} \equiv b

, we get

g^{ind_{g} (a) + ind_{g} (b)} \equiv ab \equiv g^{ind_{g} (ab)} (mod n)

. Since

g

has order

φ (n)

, the exponents agree modulo

φ (n)

. (2) Follows by repeated application of (1). (3) The equation

a^{k} \equiv 1

is equivalent to

k \cdot ind_{g} (a) \equiv 0 (mod φ (n))

, and the smallest positive

k

satisfying this is

φ (n) / g cd (ind_{g} (a), φ (n))

. □

4 Structure of $(Z / p^{k} Z)^{*}$

Theorem 7.

For an odd prime

p

and a positive integer

k

(Z / p^{k} Z)^{*}

is a cyclic group of order

φ (p^{k}) = p^{k - 1} (p - 1)

. In particular, primitive roots exist modulo

p^{k}

Remark 8.

The case

p = 2

is different:

(Z /2 Z)^{*} ≅ {1}

(Z /4 Z)^{*} ≅ Z /2 Z

, and for

k \geq 3

(Z / 2^{k} Z)^{*} ≅ Z /2 Z \times Z / 2^{k - 2} Z

(which is not cyclic).

5 The Discrete Logarithm Problem

Definition 9 (Discrete logarithm problem (DLP)).

Let

g

be a primitive root modulo a prime

p

and let

h \in (Z / p Z)^{*}

. The problem of finding

x

such that

g^{x} \equiv h (mod p)

is called the discrete logarithm problem.

Remark 10.

exp (O ((lo g p)^{1/3} (lo g lo g p)^{2/3}))

. The baby-step giant-step method solves the DLP in

O (p)

time and serves as a general-purpose approach.

Number Theory Algebra Textbook Primitive Roots Discrete Logarithm

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Primitive Roots and Discrete Logarithms — $(\mathbb{Z}/p\mathbb{Z})^*$ as a Cyclic Group

1 Definition of Primitive Roots

2 Cyclicity of $(Z / p Z)^{*}$

3 The Index (Discrete Logarithm)

4 Structure of $(Z / p^{k} Z)^{*}$

5 The Discrete Logarithm Problem

Share your expertise with the world

More from Folio Official

Introduction to Algebraic Integers — Extending the Notion of Integer

Arithmetic Functions and Multiplicative Functions — Functions on the Integers

Primes and the Fundamental Theorem of Arithmetic — The Atomic Decomposition of Integers

Chebyshev's Estimates: 0.92 x/ln x < π(x) < 1.11 x/ln x and the Prime Number Theorem

Primitive Roots and Discrete Logarithms — $(\mathbb{Z}/p\mathbb{Z})^*$ as a Cyclic Group

1 Definition of Primitive Roots

2 Cyclicity of $(Z / p Z)^{*}$

3 The Index (Discrete Logarithm)

4 Structure of $(Z / p^{k} Z)^{*}$

5 The Discrete Logarithm Problem

Share your expertise with the world

More from Folio Official

Introduction to Algebraic Integers — Extending the Notion of Integer

Arithmetic Functions and Multiplicative Functions — Functions on the Integers

Primes and the Fundamental Theorem of Arithmetic — The Atomic Decomposition of Integers

Chebyshev's Estimates: 0.92 x/ln x < π(x) < 1.11 x/ln x and the Prime Number Theorem

1 Definition of Primitive Roots

2 Cyclicity of(Z/pZ)∗

3 The Index (Discrete Logarithm)

4 Structure of(Z/pkZ)∗

5 The Discrete Logarithm Problem

Share your expertise with the world

More from Folio Official

Introduction to Algebraic Integers — Extending the Notion of Integer

Arithmetic Functions and Multiplicative Functions — Functions on the Integers

Primes and the Fundamental Theorem of Arithmetic — The Atomic Decomposition of Integers

Chebyshev's Estimates: 0.92 x/ln x < π(x) < 1.11 x/ln x and the Prime Number Theorem

1 Definition of Primitive Roots

2 Cyclicity of(Z/pZ)∗

3 The Index (Discrete Logarithm)

4 Structure of(Z/pkZ)∗

5 The Discrete Logarithm Problem

Share your expertise with the world

More from Folio Official

Introduction to Algebraic Integers — Extending the Notion of Integer

Arithmetic Functions and Multiplicative Functions — Functions on the Integers

Primes and the Fundamental Theorem of Arithmetic — The Atomic Decomposition of Integers

Chebyshev's Estimates: 0.92 x/ln x < π(x) < 1.11 x/ln x and the Prime Number Theorem

2 Cyclicity of $(Z / p Z)^{*}$

4 Structure of $(Z / p^{k} Z)^{*}$

2 Cyclicity of $(Z / p Z)^{*}$

4 Structure of $(Z / p^{k} Z)^{*}$