# Is $\mathbb Z _p^*=\{ 1, 2, 3, ... , p-1 \}$ a cyclic group?

In undergraduate course, the two groups which are most frequently used may be $$\{ 0, 1, 2, ... , p-1\}$$ and $$\{ 1, 2, ... , p-1\}$$ where $p$ is a prime.

The first one is a group under addition and in addition it is a cyclic group whose generator is $p-1$. Also we can describe it by the solution set of $x^p=1$ in ${\bf C}$.

The latter is a group under multiplication. Fermat's theorem implies that $$a^{p-1} =1~~~ (\text{mod}\;\;p)$$ for $a\in \{ 1, ... , p-1\}$. But this is not sufficient for $\{ 1, ... , p-1\}$ to be cyclic.

My question is :

$$\{ 1, ... , p-1\}$$ is cyclic ?

Thank you in advance.

• @Babak : Thank you for your distinguished editting. Commented Jan 30, 2013 at 9:44
• For a proof, see math.stackexchange.com/questions/78416/….
– lhf
Commented Jan 30, 2013 at 10:24
• A finite subgroup of the multiplicative group of a field is cyclic. Here is a short simple proof. Commented Jan 9, 2022 at 11:04

## 6 Answers

Here is the proof that $G=\mathbb{F}_p ^*$ is cyclic (in fact any finite subgroup of the multiplicative group of a field is cyclic). One needs to know that a finite abelian group is the direct product of its Sylow subgroups: $$G \simeq G_{p_1} \times ...\times G_{p_n}$$ where $p_j$ is a prime and $G_{p_j}$ has order $p_j^{n_j}$. So you can assume that the group's order is a power of a prime, say $G$ has order $q^n$. But then, if $G$ does not contain an element of order $q^n$, the order of every element divides $q^{n-1}$, that is, for all $a\in G$, $$a^{q^{n-1}}-1=0$$ in the field. But this cannot be true because the polynomial of order $q^{n-1}$ would have $q^n$ roots.

It is cyclic. A generator $a \in \mathbb F_p^*$ would satisfy $|a| = p - 1$ where $|a|$ is the order of $a$. We can find the generator as follows. Factor $p - 1$ as $p - 1 = q_1^{a_1}q_2^{a_2}\ldots q_n^{a_n}$ where $q_i$ are distinct primes, and $a_i$ are all non-zero.

1. We will try to find elements of $\mathbb F_p^*$ that have orders $q_i^{a_i}$. Since $x^{p-1} - 1 = 0$ has $p - 1$ roots (by Fermat's theorem) and $x^{p-1} - 1$ factors, for any $i$, as \begin{align*} x^{p-1} - 1 & = \left(x^{q_i^{a_i}} - 1\right)\left(1 + x^{q_i^{a_i}} + \ldots + \left(x^{q_i^{a_i}}\right)^{(p-1)q_i^{-a_i} - 1}\right), \end{align*} we know that $x^{q_i^{a_i}} - 1$ has exactly $q_i^{a_i}$ roots by counting degrees. A similar argument can be made to conclude that $x^{q_i^{a_i - 1}} - 1$ has exactly $q_i^{a_i - 1}$ roots. Therefore, there exists some $g_i \in \mathbb F_p^*$ such that $g^{q_i^{a_i}} = 1$ and $g^{q_i^{a_i - 1}} \ne 1$. We see that $|g| \mid q_i^{a_i}$ but $|g| \nmid q_i^{a_i - 1}$, so $|g| = q_i^{a_i}$.
2. Let $g = g_1g_2\ldots g_n$. Obviously $|g| \mid p - 1$, i.e., $|g| = q_1^{b_1}q_2^{b_2}\ldots q_n^{b_n}$ with $b_n \le a_n$. Write this as $$\prod_{i} g_i^{q_1^{b_1}q_2^{b_2}\ldots q_n^{b_n}} = 1.$$ Fix $j \in \{1, 2, \ldots, n\}$. Raise the above equation to the $q_k^{a_k - b_k}$-th power for all $k \ne j$ successively: \begin{align*} \prod_{i} g_i^{(p-1)q_j^{b_j-a_j}} & = 1. \end{align*} For $i \ne j$, the factor $g_i^{(p-1)q_j^{b_j-a_j}} = 1$ because $|g_i| = q_i^{a_i} \mid (p-1)q_j^{b_j - a_j}$. So the only non-identity factor is the term $i = j$: $$g_j^{(p-1)q_j^{b_j-a_j}} = 1.$$ This means $|g_j| \mid (p-1)q_j^{b_j - a_j} = (p-1)q_j^{-a_j}q_j^{b_j}$, but $|g_j| = q_j^{a_j}$ and $q_j \nmid (p-1)q_j^{-a_j}$, we must have $b_j = a_j$.
• What conditions will not follow if I change the group to $\mathbb{Z}_m^*$ ? Commented Sep 26, 2018 at 9:12

It is a general theorem that every finite subgroup of the multiplicative group of a field is cyclic. That is, if $F$ is any field, the set $F^*$ of all non-zero elements in $F$ is always a group under the multiplication in the field. Any finite subgroup of $F^*$ is cyclic. Thus the group $\mathbb Z_p^*$ that you describe is cyclic, since $\mathbb Z_p$ is a field.

There are several proofs for this result, one of them uses a characterization of finite cyclic groups that can be applied directly to $Z_p^*$. The characterization of finite cyclic groups is that if $G$ is a finite group of order $n$ then $G$ is cyclic if, and only if, for very $d$ that divides $n$ the group $G$ has at most one subgroup of order $d$. The proof is not very hard and is classical. It should be noted that the proof does not point to any generator, but only proves the existence of a generator. Consequently, using this theorem to prove that $\mathbb Z_p^*$ is cyclic does not produce a generator (known as a primitive element). There are no trivial ways to produce such primitive elements.

A somewhat similar situation is the result from Galois theory that every finite separable extension is generated by one element (a primitive element again). The general proof is again non-constructive and finding primitive elements for any given field extension can be very hard.

Consider the field $\mathbb{F}_{p}$ - the field with $p$ elements.

The group $\{1,...p\}$ is $\mathbb{F}_{p}^{*}$, that is all the invertible elements of $\mathbb{F}_{p}$.

This is a cyclic group as it is a finite subgroup of a field (with respect to multiplication).

The group $\{1,2,\ldots,p-1\}$ under multiplication is indeed cyclic. It can be shown that there exists a primitive root $\pmod p$ for every prime $p$. This will now generate the multiplicative group $\{1,2,\ldots,p-1\}$.

[This is just a repetition of the standard proof, mentioned for eg in KConrad’s notes and Weil’s Number Theory for Beginners]

We can briefly recall basic properties of cyclic groups.

Consider a cyclic group $${ G = \langle g \rangle }$$ of size $${ n .}$$ Let $${ G ^{'} \subseteq G }$$ be a subgroup of size $${ m .}$$ (By Lagrange’s theorem, $${ m \vert n }$$). We can ask ourselves:

Is subgroup $${ G ^{'} }$$ cyclic too?
Consider $${ \lbrace x \in \mathbb{Z} : g ^x \in G ^{'} \rbrace. }$$ We see it is a subgroup of $${ \mathbb{Z} ,}$$ hence is of the form $${ d \mathbb{Z} }$$ with $${ d \geq 0 .}$$ Note this set contains $${ n ,}$$ hence $${ n \in d \mathbb{Z} }$$ that is $${ d \vert n }$$ (especially $${ d > 0 }$$).
So $${ G ^{'} }$$ $${ = \lbrace g ^x : x \in d \mathbb{Z} \rbrace }$$ $${ = \langle g ^d \rangle }$$ is cyclic. The smallest positive power of $${ g ^d }$$ which equals $${ 1 }$$ is $${ (g ^d) ^{\frac{n}{d}} = 1 .}$$ So $${ G ^{'} }$$ $${ = \langle g ^d \rangle }$$ has size $${ m = \frac{n}{d} ,}$$ that is the parameter $${ d = \frac{n}{m} .}$$ Finally $${ G ^{'} = \langle g ^{\frac{n}{m}} \rangle .}$$

So infact for every positive divisor $${ m \vert n ,}$$ there is a unique subgroup of size $${ m ,}$$ given by $${ \langle g ^{\frac{n}{m}} \rangle .}$$

What are all the generators of $${ G }$$ and $${ G ^{'} }$$?
Say $${ g ^a }$$ is a generator of $${ G = \langle g \rangle. }$$ Note

{ \begin{align*} &\langle g ^a \rangle = \langle g \rangle \\ \iff &\langle g \rangle \subseteq \langle g ^a \rangle \\ \iff &g = g ^{at} \text{ for some } t \in \mathbb{Z} \\ \iff &g ^{at - 1} = 1 \text{ for some } t \in \mathbb{Z} \\ \iff &at-1 \in n \mathbb{Z} \text{ for some } t \in \mathbb{Z} \\ \iff &1 \in a\mathbb{Z} + n\mathbb{Z} \\ \iff &1 \in \text{gcd}(a,n) \mathbb{Z} \\ \iff &\text{gcd}(a,n) = 1. \end{align*} }

So the distinct generators of $${ G = \langle g \rangle }$$ are $${ \lbrace g ^a : 1 \leq a \leq n, \, \text{gcd}(a,n) = 1 \rbrace .}$$ The size of this set is defined as $${ \varphi(n) .}$$

We saw the distinct generators of any finite cyclic group $${ G = \langle g \rangle }$$ are $${ \lbrace g ^a : 1 \leq a \leq \text{ord}(g), \, \text{gcd}(a, \text{ord}(g)) = 1 \rbrace .}$$
Applying this to $${ G ^{'} = \langle g ^{\frac{n}{m}} \rangle ,}$$ we see the distinct generators of subgroup $${ G ^{'} = \langle g ^{\frac{n}{m}} \rangle }$$ are $${ \lbrace g ^{\frac{n}{m} a} : 1 \leq a \leq m, \, \text{gcd}(a, m) = 1 \rbrace. }$$

Now consider the field $${ \mathbb{Z}/p\mathbb{Z} ,}$$ and its group of invertibles $${ (\mathbb{Z}/p\mathbb{Z}) ^{\times} = \lbrace 1, \ldots, p-1 \rbrace. }$$

We can study the structure of the group $${ (\mathbb{Z}/p\mathbb{Z}) ^{\times} .}$$

For every $${ g }$$ in the group, $${ \text{ord}(g) }$$ must divide $${ p-1 .}$$ So for every positive divisor $${ d \vert p - 1 ,}$$ consider $${ O _d := \lbrace \text{order } d \text{ elements in } (\mathbb{Z}/p\mathbb{Z}) ^{\times} \rbrace , }$$ $${ S _d := \lbrace \text{solutions to } g ^d = 1 \text{ in } (\mathbb{Z}/p\mathbb{Z}) ^{\times} \rbrace . }$$

If it so happens that $${ O _{p-1} \neq \emptyset, }$$ then it has a generator of $${ (\mathbb{Z}/p\mathbb{Z}) ^{\times} .}$$ Let us check if $${ O _{p-1} \neq \emptyset .}$$

Firstly, the group is disjoint union of $${ O _d }$$ over all positive divisors $${ d \vert p - 1 .}$$ Hence $${ p-1 = \sum _{d \vert p - 1} \#(O _d) .}$$

We can also bound the size of each summand:
Let $${ d }$$ be a positive divisor $${ d \vert p - 1 .}$$ Now $${ O _{d} \subseteq S _d }.$$ But the polynomial $${ X ^d - 1 \in (\mathbb{Z}/p\mathbb{Z})[X] }$$ has almost $${ d }$$ roots in $${ (\mathbb{Z}/p\mathbb{Z}) }.$$ Hence $${ \#( O _d ) \leq \#( S _d ) \leq d .}$$

Let $${ d }$$ be a positive divisor $${ d \vert p - 1 }$$ with $${ O _d \neq \emptyset .}$$
Now we can pick a $${ g \in O _d ,}$$ and look at the subgroup $${ \langle g \rangle }$$ of size $${ d .}$$ Since $${ \langle g \rangle \subseteq S _d ,}$$ and sizes $${ \#\langle g \rangle = d }$$ and $${ \# (S _d) \leq d },$$ we have $${ \langle g \rangle = S _d .}$$ Hence

{ \begin{align*} O _d &= \lbrace \text{order } d \text{ elements in } S _d \rbrace \\ &= \lbrace \text{order } d \text{ elements in } \langle g \rangle \rbrace \\ &= \lbrace \text{generators of } \langle g \rangle \rbrace \\ &= \lbrace g ^a : 1 \leq a \leq d, \text{gcd}(a,d) = 1 \rbrace. \end{align*} }

Especially $${ \# (O _d) = \varphi (d) .}$$

So we have { \begin{align*} p-1 &= \sum _{d \vert p - 1} \# (O _d) \\ &= \sum _{d \vert p - 1 ; \, O _d \neq \emptyset} \# (O _d) \\ &= \sum _{d \vert p - 1 ; \, O _d \neq \emptyset} \varphi(d). \end{align*} }

But we already have $${ p - 1 = \sum _{d \vert p - 1} \varphi(d) .}$$

Because consider a cyclic group $${ G = \langle g \rangle }$$ of size $${ n .}$$ Now { \begin{align*} n &= \sum _{d \vert n} \#\lbrace \text{order } d \text{ elements in } G \rbrace. \end{align*} } Let $${ x }$$ be a generic order $${ d }$$ element in $${ G. }$$ It generates a subgroup $${ \langle x \rangle }$$ of size $${ d .}$$ But there is a unique subgroup of size $${ d ,}$$ namely $${ \langle g ^{\frac{n}{d}} \rangle .}$$ Hence $${ \langle x \rangle = \langle g ^{\frac{n}{d}} \rangle },$$ that is $${ x }$$ is a generator of $${ \langle g ^{\frac{n}{d}} \rangle .}$$ So above equation becomes { \begin{align*} n &= \sum _{d \vert n} \#\lbrace \text{order } d \text{ elements in } \langle g \rangle \rbrace \\ &= \sum _{d \vert n} \# \lbrace \text{generators of } \langle g ^{\frac{n}{d}} \rangle \rbrace \\ &= \sum _{d \vert n} \varphi(d), \end{align*}} as needed.

Hence $${ \sum _{d \vert p - 1 ; \, O _d \neq \emptyset} \varphi(d) = p - 1 = \sum _{d \vert p - 1} \varphi(d) ,}$$ giving $${ O _d \neq \emptyset }$$ for every positive divisor $${ d \vert p - 1 .}$$

Especially $${ O _{p-1} \neq \emptyset ,}$$ giving a generator of $${ (\mathbb{Z}/p\mathbb{Z}) ^{\times} .}$$

Above counting argument is non-constructive :/ ! It does not explicitly give a generator of $${ (\mathbb{Z}/p\mathbb{Z}) ^{\times} .}$$