The Fundamental Theorem of Finite Cyclic Groups

The Fundamental Theorem of Cyclic Groups provides guarantees about the existence of cyclic subgroups within a cyclic group.

In the context of the Number Theoretic Transform (NTT) of polynomials over a finite field, and also the FRI operation in ZK-STARKs, we need multiplicative subgroups whose order (number of elements) is a power of two. The Fundamental Theorem of Cyclic Groups enables us to quickly determine if a particular finite field has a multiplicative subgroup with that order or not.

We will cover the following as preliminaries, then get to the Fundamental Theorem of Cyclic Groups:

Definition of a Subgroup
Order of a Group or Subgroup
Powers of an Element in a Multiplicative Group
Cyclic Subgroups, Cyclic Groups, and Their Generators

1. Definition of a Subgroup

Given a group $G$, a subset $H$ of $G$ is a subgroup of $G$ if $H$ forms a group with respect to the group operation in $G$. In other words, if we restrict ourselves to elements of H but keep using the group operation of G, the criteria for a group all still hold. Most importantly, the operation must be closed in H, so whenever we apply the operation on two elements of H, we must get out another element of H.

Example of Subgroups

The set of integers modulo 8 under addition form a group $\mathbb{Z}_8 = (\{0, 1, 2, 3, 4, 5, 6, 7\}, +)$.. $H_1=(\{0, 2, 4, 6\}, +)$ and $H_2=(\{0, 4\}, +)$ are both subgroups of $\mathbb{Z}_8$. On the other hand, $H_3=(\{0, 2\}, +)$ is not, because $(2+2) \not \in H_3$

2. Order of a Group or Subgroup

The order of a group $G$, denoted by $|G|$, is the number of its elements. If a group is not finite, its order is said to be infinite.

Example for the order of a group and subgroup

Consider the group $\mathbb{Z}_8$ of the example above. The order of $\mathbb{Z}_8$ is 8, meaning $|\mathbb{Z}_8| = 8$ (since there are exactly 8 elements in the group). Moreover, the order of the subgroup $H = (\{0, 2, 4, 6\}, +)$ is 4 (i.e. $|H| = 4$).

3. Powers of an element in a multiplicative group

If $g \in G$, the powers of the element $g$, denoted by $\langle g\rangle$, form the set $\{g^k: k\in\mathbb{Z}\}$. For example, consider the group of non-zero integers under multiplication modulo 7, $G =\{1, 2, 3, 4, 5, 6\}$. The powers of the element $3$ in $G$ are as follows:

$$ \begin{aligned} \text{Powers of $3$} = \langle 3\rangle = \{3^0, 3^1, 3^2, 3^3, 3^4, 3^5, 3^6, \dots\}. \end{aligned}$$

Since:

$$ \begin{aligned} &3^0 = 1,\\ &3^1 = 3,\\ &3^2 = 9 \equiv 2,\\ &3^3 = 9 * 3 \equiv 2 * 3 \equiv 6,\\ &3^4 = 9 * 9 \equiv 2 * 2 \equiv 4,\\ &3^5 = 9 * 9 * 3 \equiv 2 * 2 * 3 \equiv 12 \equiv 5,\\ &3^6 = 9 * 9 * 9 \equiv 2 * 2 * 2 \equiv 8 \equiv 1. \end{aligned}$$

How about $3^7$?

$$ 3^7 = 3^6 * 3 \equiv 1 * 3 \equiv 3 \pmod{7}.$$

Thus, $\langle 3\rangle = \{1, 2, 3, 4, 5, 6\}$. For every power $3^k$ with $k>6$, the result will be one of the elements already in this list.

Exercise: Find the set generated by the element $4$.

The powers of an arbitrary element form a Subgroup

Let $g$ be an arbitrary element in $G$. The set of powers of the element $g$ forms a subgroup. In other words,

$$ \langle g\rangle = \{g^k: k\in\mathbb{Z}\},$$

is a subgroup of $G$.

Proof. See the appendix

4. Cyclic Subgroups, Cyclic Groups, and Their Generators

Let $g$ be an arbitrary element in $G$, then the subgroup $\langle g\rangle = \{g^k: k\in\mathbb{Z}\}$ is called the cyclic subgroup of $G$ generated by $g$. For example, consider the group of non-zero integers under multiplication modulo 7, $G =\{1, 2, 3, 4, 5, 6\}$. The cyclic subgroup generated by the element $2$ is:

$$ \langle 2 \rangle = \{2^0=\boxed{1}, 2^1=\boxed{2}, 2^2=\boxed{4},2^3=\boxed{1},2^4=\boxed{2},2^5=\boxed{4},2^6=\boxed{1}\}=\{1, 2, 4\}$$

Exercise: Find the subgroup generated by the element $6$.

Definition of a Cyclic Group

Let $g$ be an arbitrary element in $G$. If $G = \langle g\rangle$, then we say that $G$ is a cyclic group and that $g$ is a generator of $G$. In other words, a group is cyclic if it contains at least one element that generates all the elements of the group.

Example of Cyclic Group and Generators

Consider the group of non-zero integers under multiplication modulo 7, $G =\{1, 2, 3, 4, 5, 6\}$. Since $\langle 3 \rangle = G$, as shown above, then $G$ is a cyclic group and $3$ is a generator of $G$.

Note that $\langle 2 \rangle = \{1, 2, 4\}\neq G$, which means that the element $2$ is not a generator of $G$, but rather 2 generates a subgroup of $G$.

Exercise: Determine whether $5$ is a generator of $G$

Generators of Cyclic Groups Are Not Necessarily Unique

Cyclic groups have at least one generator, but the generator does not have to be unique. In other words, a cyclic group can have multiple generators, any of which generates the entire group. The same is true for cyclic subgroups.

As you saw in the example and exercise above, the elements $3$ and $5$ are both generators of the group $G =\{1, 2, 3, 4, 5, 6\}$.

For another example, consider the group of non-zero integers under multiplication modulo 5. i.e, $\{1, 2 ,3, 4\}$. The elements $2$ and $3$ generate whole group.

$$ \begin{aligned} &2^0 =1,\qquad\qquad\qquad\qquad 3^0 =1,\\ &2^1 =2,\qquad\qquad\qquad\qquad 3^1 =3,\\ &2^2 =4,\qquad\qquad\qquad\qquad 3^2 =4,\\ &2^3 =3,\qquad\qquad\qquad\qquad3^3 =2.\\ \end{aligned}$$

The Fundamental Theorem of Finite Cyclic Groups

The Fundamental Theorem of Finite Cyclic Groups makes three claims. Let $G$ be a finite cyclic group, and let $H$ be a subgroup of $G$.

$H$ is necessarily finite and cyclic (meaning $H$ has a generator).
The order of $H$ (the number of elements it has) is a factor of the order of $G$. In other words, the order of $H$ divides the order of $G$. For example, suppose the order of $G$ is 6. We automatically know a subgroup of order 5 cannot exist, since 5 does not divide 6.
If $q$ is the order of $G$ and $n$ divides $q$, then a subgroup of size $n$ necessarily exists and is unique. In fact, we can immediately find a generator for it: if $g$ is a generator of $G$, then $g^\frac{q}{n}$ is a generator for a subgroup of size $n$. This subgroup of size $n$ is equal to $\langle g^\frac{q}{n} \rangle$. We will show examples of this shortly.

Connection to Lagrange’s Theorem

Statement (2) of the Fundamental Theorem of Finite Cyclic Groups holds for any finite group $G$, even if $G$ is not cyclic. This general result is known as Lagrange’s Theorem.

For brevity, we will call this the Fundamental Theorem of Cyclic Groups, with the understanding that we are dealing with finite groups.

Examples of Using the Fundamental Theorem of Cyclic Groups

Let’s use $G = \{1,2,3,4,5,6\}$ under multiplication modulo 7 as our cyclic group. We’ve already shown that $g = 3$ generates the whole group.

The subgroup of order 1

Using the Fundamental Theorem of Cyclic Groups, we know that $G$ has a subgroup of order 1, since 1 divides 6. Now let’s find a generator for this subgroup. Since $k = 1$, we have $3^{\frac{6}{1}} \equiv 1\pmod{7}$. The identity element $1$ is clearly a generator of the subgroup of size one.

The subgroup of order 2

Now let’s find the subgroup of size 2. We know it exists because 2 divides 6. Here, we have $g = 3$, $n = 6$, and $k = 2$. Plugging into the formula, we get $g^{n/k} = 3^{6/2} = 3^3 \equiv 6\mod{7}$. The element $6$ generates the subgroup of order 2 with elements $\{1, 6\}$.

The subgroup of order 3

Since 3 divides 6, there exists a subgroup of order 3. Moreover, the element $3^{\frac{n}{k}} = 3^{\frac{6}{3}} = 3^{2} \equiv 2\pmod{7}$ is a generator for this subgroup, $\langle 2\rangle = \{2^0, 2^1, 2^2\} =\{1, 2, 4\}.$

The subgroup of order 4, 5

There are no subgroups of order 4 and 5 because these numbers do not divide 6.

The subgroup of order 6

Since 6 divides 6, there exists a subgroup of order 6. Moreover, $3^{\frac{n}{k}} = 3^{\frac{6}{6}} = 3^{1} = 3$ is a generator of this subgroup:

$$ \langle 3 \rangle =\{1, 2, 3, 4, 5, 6\} = G.$$

Exercise: Consider the group with elements $G = \{1,2,3,4,5,6,7,8,9,10\}$ under multiplication module 11.

Find a generator for this group.
The group has a subgroup of order 5, since 5 divides the order of $G$, which is 10. Find a generator for this subgroup and calculate the subgroup it generates.

Multiplicative Subgroup of Order $n$ in a Finite Field

We can find multiplicative subgroups of specific order in a finite field. First, let’s see the definition of finite fields:

By definition, a field $(\mathbb{F}, + , *)$ consists of two Abelian (binary operators are commutative) groups:

Additive group: $(\mathbb{F}, +)$, which is Abelian and finite in a finite field.
Multiplicative group: $(\mathbb{F^*}, *)$ (where $\mathbb{F}^* = \mathbb{F}\setminus\{0\}$), which is also Abelian and finite in a finite field.

Note that $\mathbb{F}_q$ denotes a field with $q$ elements, while $\mathbb{F}^*_q$ (the multiplicative group of $\mathbb{F}_q$) has $q-1$ elements.

In the following theorem, we see that every finite field necessarily contains a multiplicative subgroup of order $q – 1$ (with $0$ omitted).

Theorem 1: The Multiplicative Group $\mathbb{F}^*_q$ is Cyclic of Order $q-1$.

If $\mathbb{F}_q$ is a finite field with order $q$, then its multiplicative group $\mathbb{F}^*_q$ is cyclic of order $q-1$.

That $\mathbb{F}^*_q$ forms a group of order $q-1$ follows immediately from the definition of a finite field.

Since proving the cyclicity of the multiplicative group would take us beyond the scope of this article, we will take it as a given fact.

A cyclic group has a generator, therefore we know that some $g\in \mathbb{F}^*_q$ exists such that

$$ \mathbb{F}^*_q = \{1, g^1, g^2, \dots, g^{q-2}\} = \langle g \rangle.$$

Primitive Elements in a Finite Field (Generators)

In field theory, a primitive element of a finite field $\mathbb{F}_q$ is a generator of the multiplicative group of the field. The element $g$ in Theorem 1 is a primitive element in $\mathbb{F}_q$.

The Python code below uses the galois library to identify primitive elements (generators) in $\mathbb{F}_7$.

import galois

GF = galois.GF(7)

primitive_elements = GF.primitive_elements
print("Primitive elements:", primitive_elements)
# Primitive elements: [3 5]

# Alternatively, find a single primitive element
# suitable when there are a lot of primitive elements
primitive_element = GF.primitive_element
print("A primitive element:", primitive_element)
# A primitive element: 3

Exercise: Use Python to find all the primitive elements of the multiplicative group of the field $\mathbb{F}_{11}$.

Corollary 1: Testing for Subgroup of Order $n$ — Existence via Divisors in a Finite Field

A useful corollary is that we can quickly check whether a subgroup of a certain size exists or not by listing all the divisors of $n$. For example, consider the field $\mathbb{F}_{41}$, which has a multiplicative group $\mathbb{F}_{41}^*$ with order 40. We can quickly check that $\mathbb{F}_{41}^*$ has a subgroup of size 8 because 8 divides 40.

As another example, consider the field $\mathbb{F}_{17}$, whose multiplicative group $\mathbb{F}_{17}^*$ has order 16. Since 8 divides 16, $\mathbb{F}_{17}^*$ has a subgroup of size 8. Similarly, it has a subgroup of size 4, because 4 divides 16, and, as you might guess, $\mathbb{F}_{17}$ also has a subgroup of size 2.

To find a generator for a multiplicative subgroup of a given size, we can use statement (3) of the Fundamental Theorem above. The size of $\mathbb{F}_{q}^*$ is $q-1$, so if we have a primitive element $g$ and want a multiplicative subgroup of order $n$, we can calculate $g^\frac{q-1}{n}$ for any primitive element $g$.

All In One Example

Consider the finite field $\mathbb{F}_{17} =\{0, 1, 2, \dots, 16\}$. For a given $n$, we want to find a multiplicative subgroup of order $n$ in $\mathbb{F}_{17}$ using the Fundamental Theorem of Finite Cyclic Groups.

Since the multiplicative subgroup $\mathbb{F}_{17}^*$ has order $q-1=17-1=16$, we know from statement (2) of the Fundamental Theorem of Cyclic Groups that it has subgroups of orders 1, 2, 4, 8, and 16, with the last one being the group itself.

These subgroups are cyclic, so each has at least one generator. From statement (3) of the theorem, we know that a generator for each subgroup is given by $g^\frac{q-1}{n}$ , where $g$ is a generator of the full multiplicative group and n is the size of our desired subgroup.

Therefore, to generate the subgroups, the first step is to find a generator of $\mathbb{F}_{17}^*$, which is a primitive element of $\mathbb{F}_{17}$.

The generator of $\mathbb{F}^*_{17}$

Recall from Theorem 1 that $\mathbb{F}^*_{17}$ is a cyclic group. To show that $mathbb{F}^_{17}$* can be generated by the element $3$, we can calculate all powers of $3$ as follows:

$$ \begin{aligned} &3^0 = \boxed{1},\\ &3^1 = \boxed{3},\\ &3^2 = \boxed{9},\\ &3^3 \equiv 9 * 3 \equiv \boxed{10},\space\space (27 – 17 = 10)\\ &3^4 \equiv 10 * 3\equiv \boxed{13},\space\space(30 – 17 = 13)\\ &3^5 \equiv 13 * 3 \equiv \boxed{5},\space\space(39 – 2*17 = 5)\\ &3^6 \equiv 5 * 3 \equiv \boxed{15},\\ &3^7 \equiv 15 * 3 \equiv \boxed{11},\space\space(45 – 2*17 = 11)\\ &3^8 \equiv 11 * 3 \equiv \boxed{16},\space\space(33 – 17 = 16)\\ &3^9 \equiv 16 * 3 \equiv \boxed{14},\space\space(48 – 2*17 = 14)\\ &3^{10} \equiv 14 * 3 \equiv \boxed{8},\space\space(42 – 2*17 = 8)\\ &3^{11} \equiv 8 * 3 \equiv \boxed{7},\space\space(24 – 17 = 7)\\ &3^{12} \equiv 7 * 3 \equiv \boxed{4},\space\space(21 – 17 = 4)\\ &3^{13} \equiv 4 * 3 \equiv \boxed{12},\\ &3^{14} \equiv 12 * 3 \equiv \boxed{2},\space\space(36 – 2*17 = 2)\\ &3^{15} \equiv 2 * 3 \equiv \boxed{6},\\ &3^{16} = 6 * 3 \equiv \boxed{1},\space\space(18 – 17 = 1). \end{aligned}$$

How about $3^{17}$?

$$ 3^{17} = 3^{16} * 3 \equiv 1 * 3 = 3.$$

You can see that for all $i \ge 17$, the element $3^i$ is equal to one of the $3^0, 3^1, 3^2, \dots, 3^{16}$. You can also see that every value in {1,2,…,16} shows up somewhere in the list of powers of 3. Then, $\langle 3 \rangle = \{1, 2, \dots, 16\} = \mathbb{F}^*_{17}$.

This generator can be found in Python code with galois.primitive_elements.

import galois

GF = galois.GF(17)

primitive_element = GF.primitive_element
print("A primitive element:", primitive_element)
# A primitive element: 3

Finding the subgroup of order $n$ in $\mathbb{F}^*_{17}$

Suppose we want to determine whether a multiplicative subgroup of order $n=4$ exists in the finite field $\mathbb{F}_q = \mathbb{F}_{17}$. Note that the multiplicative group of $\mathbb{F}_q$ has size $q-1$. For $\mathbb{F}_{17}$, the multiplicative group $\mathbb{F}_{17}^*$ has $q-1 = 17-1 = 16$ elements.

Recall from the Fundamental Theorem of Finite Cyclic Groups that since $n$ divides $q-1$ (explicitly, $4$ divides 16), then $g^{\frac{q-1}{n}}$ is a generator and $\langle g^{\frac{q-1}{n}}\rangle$ is a subgroup of size 4.

$$ g^{\frac{q-1}{n}} = 3^{\frac{16}{4}} = 3^4 \equiv 13\pmod{17}.$$

Thus, 13 is a generator for the subgroup of size 4 in $*\mathbb{F}^*_{17}*$ and

$$ \langle 13 \rangle = \{13^0 = \boxed{1}, 13^1 = \boxed{13}, 13^2\equiv\boxed{16}, 13^3\equiv\boxed{4}, 13^4\equiv\boxed{1}, 13^5\equiv\boxed{13}, \dots\}.$$

Explicitly, $\{1, 13, 16, 4\}$ is the subgroup.

Exercise: Compute the multiplicative subgroups of order $2$ and $8$.

Summary

The goal is to find the multiplicative subgroups of size $n$ in the field $\mathbb{F}_q$.
If $G = \langle g\rangle = \{g^k: k\in\mathbb{Z}\}$, then $G$ is a cyclic group, and $g$ is a generator of $G$.
If $\mathbb{F}_q$ is a finite field of order $q$, then $(\mathbb{F}^*_q, .)$ is a cyclic group of order $q-1$.
The Fundamental Theorem of Cyclic Groups states that the finite field $\mathbb{F}_q$ has a subgroup of size $n$ if and only if $n$ divides $q-1$. Moreover, a generator of this subgroup is $g^{\frac{q-1}{n}}$, where $g$ is a generator of the multiplicative group $\mathbb{F}^*_q$.

Appendix

We will check the three conditions necessary for $\langle g \rangle$ to be a subgroup of $G$.

Identity: Since $1 = g^0$, then $1 \in \langle g \rangle$.

Closure: Suppose $a, b \in \langle g \rangle$. Then we know $a = g^k$ and $b = g^m$ for some $k, m$. Applying the group operation gives

$$ ab = g^kg^m = g^{k+m}.$$

Since $k+m\in\mathbb{Z}$, hence $ab\in \langle g \rangle$.

Inverse: Suppose $a\in \langle g \rangle$. Then $a = g^k$ for some $k$,

$$ a^{-1} = (g^k)^{-1} = g^{-k}.$$

Since $-k\in\mathbb{Z}$, so $a^{-1} \in \langle g \rangle$.

Exercises

What are all the orders of the multiplicative subgroups of $\mathbb{F}_{31}$ and a generator for each subgroup?

What are all the orders of the multiplicative subgroups of $\mathbb{F}_{5}$ and a generator for each subgroup?

What are all the orders of the multiplicative subgroups of $\mathbb{F}_{51}$ and a generator for each subgroup?