Generators of Finite Cyclic Groups

After relating the size of a cyclic group to the order of its generator, we now ask which powers of a generator are also generators. This is a precise arithmetic question. If

G=\langle a\rangle

has order

n

, then

a^r

generates

G

exactly when

r

is relatively prime to

n

. This test is one of the most useful facts about finite cyclic groups. In this lesson, students will prove the greatest common divisor criterion and apply it to find all generators of a finite cyclic group.

Let

(G,\circ)

be a finite group and let

a\in G

such that

\begin{equation*} G=\langle a\rangle \end{equation*}

and

\begin{equation*} |G|=n>1. \end{equation*}

r

is a positive integer with

1\leq r<n

, then

\begin{equation*} G=\langle a^r\rangle \iff \operatorname{gcd}(r,n)=1. \end{equation*}

After relating the size of a cyclic group to the order of its generator, we now ask which powers of a generator are also generators. This is a precise arithmetic question. If

G=\langle a\rangle

has order

n

, then

a^r

generates

G

exactly when

r

is relatively prime to

n

Let

(G,\circ)

be a finite group and let

a\in G

such that

\begin{equation*} G=\langle a\rangle \end{equation*}

and

\begin{equation*} |G|=n>1. \end{equation*}

r

is a positive integer with

1\leq r<n

, then

\begin{equation*} G=\langle a^r\rangle \iff \operatorname{gcd}(r,n)=1. \end{equation*}

Given that

(G,\circ)

is a finite group,

a\in G

G=\langle a\rangle

, and

|G|=n>1

. Let

r\in\mathbb{N}

such that

1\leq r<n

. To prove that

\begin{equation*} G=\langle a^r\rangle \iff \operatorname{gcd}(r,n)=1. \end{equation*}

Since

G=\langle a\rangle

and

|G|=n

, we get

\begin{equation*} o(a)=n. \end{equation*}

Using the formula for the order of a power,

\begin{equation*} o(a^r)=\frac{n}{\operatorname{gcd}(r,n)}. \end{equation*}

[1] To prove that

G=\langle a^r\rangle \implies \operatorname{gcd}(r,n)=1

. Let

\begin{equation*} G=\langle a^r\rangle. \end{equation*}

Then

a^r

is a generator of

G

, so

\begin{equation*} o(a^r)=|G|=n. \end{equation*}

Therefore

\begin{align*} \frac{n}{\operatorname{gcd}(r,n)}=n &\implies \operatorname{gcd}(r,n)=1. \end{align*}

[2] To prove that

\operatorname{gcd}(r,n)=1 \implies G=\langle a^r\rangle

. Let

\begin{equation*} \operatorname{gcd}(r,n)=1. \end{equation*}

Then

\begin{align*} o(a^r) &=\frac{n}{\operatorname{gcd}(r,n)}\\ &=\frac{n}{1}\\ &=n. \end{align*}

Thus

\begin{equation*} |\langle a^r\rangle|=n. \end{equation*}

Since

\langle a^r\rangle\subseteq G

and

|G|=n

, we get

\begin{equation*} G=\langle a^r\rangle. \end{equation*}

Hence,

\begin{equation*} G=\langle a^r\rangle \iff \operatorname{gcd}(r,n)=1. \end{equation*}

\square

The theorem gives a quick test for generators. In a cyclic group of order

n

, the powers

a^r

with

\operatorname{gcd}(r,n)=1

are exactly the generators. Powers with a common factor with

n

generate a smaller cyclic subgroup. This explains why

\overline{1}

and

\overline{5}

generate

\mathbb{Z}_6

, but

\overline{2}

does not.

Let

G=\langle a\rangle

and

|G|=8

. The integers

r

with

1\leq r<8

and

\operatorname{gcd}(r,8)=1

are

\begin{equation*} 1,3,5,7. \end{equation*}

Therefore the generators of

G

are

\begin{equation*} a,\;a^3,\;a^5,\;a^7. \end{equation*}

Let

G=\langle a\rangle

and

|G|=12

. The integers

r

with

1\leq r<12

and

\operatorname{gcd}(r,12)=1

are

\begin{equation*} 1,5,7,11. \end{equation*}

Thus the generators of

G

are

\begin{equation*} a,\;a^5,\;a^7,\;a^{11}. \end{equation*}

Let

G=\langle a\rangle

be a cyclic group of order

15

. Find all generators of

G

Let

G=\langle a\rangle

be a cyclic group of order

15

. To find all generators of

G

. The element

a^r

is a generator of

G

if and only if

\begin{equation*} \operatorname{gcd}(r,15)=1. \end{equation*}

For

1\leq r<15

, the integers relatively prime to

15

are

\begin{equation*} 1,2,4,7,8,11,13,14. \end{equation*}

Therefore the generators are

\begin{equation*} a,\;a^2,\;a^4,\;a^7,\;a^8,\;a^{11},\;a^{13},\;a^{14}. \end{equation*}

Hence, these are all generators of

G

\square

Let

G=\langle a\rangle

be a cyclic group of order

18

. Determine whether

a^6

is a generator of

G

Let

G=\langle a\rangle

be a cyclic group of order

18

. To determine whether

a^6

is a generator of

G

. By the generator criterion,

a^6

is a generator if and only if

\begin{equation*} \operatorname{gcd}(6,18)=1. \end{equation*}

But

\begin{equation*} \operatorname{gcd}(6,18)=6. \end{equation*}

Therefore

a^6

is not a generator of

G

. Also,

\begin{align*} o(a^6) &=\frac{18}{\operatorname{gcd}(6,18)}\\ &=\frac{18}{6}\\ &=3. \end{align*}

Hence,

a^6

is not a generator of

G

\square

Use the calculator below to find all exponents

r

such that

a^r

generates a cyclic group of order

n

. Enter

n

. The calculator lists all

r

with

1\leq r<n

and

\operatorname{gcd}(r,n)=1

. These exponents give all generators of the form

a^r

[1] State the generator criterion for

a^r

in a cyclic group of order

n

. [2] Find all generators of a cyclic group of order

10

. [3] Determine whether

a^4

is a generator when

o(a)=14

. [4] Determine the order of

a^4

when

o(a)=14

. [5] How many generators does a cyclic group of order

9

have?

[1]

a^r

is a generator if and only if

\operatorname{gcd}(r,n)=1

. [2] The generators are

a,a^3,a^7,a^9

. [3] No, because

\operatorname{gcd}(4,14)=2

. [4]

o(a^4)=14/\operatorname{gcd}(4,14)=7

. [5] The generators are

a,a^2,a^4,a^5,a^7,a^8

, so there are

6

generators.

Exactly when

\operatorname{gcd}(r,n)=1

Then

a^r

generates a proper cyclic subgroup.

Yes. It corresponds to the exponent

n-1

, which is relatively prime to

n

It equals the number of integers between

1

and

n

that are relatively prime to

n

BMLabs Mathematics

BMLabs Mathematics

Generators of Finite Cyclic Groups

Generators of Finite Cyclic Groups

GENERATOR EXPONENTS

PRIME ORDER CYCLIC GROUPS

Coordinates and Locus

Invariants under Orthogonal Transformation