Cyclic Numbers (Group Theory)

In group theory, a cyclic number is a positive integer such that every group with that number of elements must be cyclic.

For clarity, we should define a few terms:

The order of a group is the number of elements in that group. Here, we will denote the order of a group $G$ as $|G|$. If the number of elements is infinite, then the order of $G$ is infinite, but here we will deal exclusively with finite groups.

The order of an element $f\in G$ is the smallest $a>0$ such that $f^a=e$, where $e$ is the identity element in $G$. The order of $f$ is denoted $\mathrm{ord}(f)$. If there is no such $a>0$, then we say that $f$ has infinite order. However, we will soon see that we don't need to worry about this case.

We will need the following important theorem relating the order of elements in a group to the order of a group:

If $G$ is a group, then for all $g\in G$, $\mathrm{ord}(g)$ divides $|G|$.

This is a direct consequence of Lagrange's Theorem.

A cyclic group is a group $G$ such that every element of $G$ can be written as $g^k$, for some element $g\in G$ and $k\in\mathbb{Z}$. In other words, a cyclic group is a group that can be generated by only $1$ element.

Our goal here is to find exactly which numbers are cyclic and which are not. Let us start with some simple results and see where they take us.

Any cyclic number must be squarefree: To prove this, suppose we have a non-squarefree number $N=Kp^2$, where $p$ is a prime. We will prove that $N$ is not cyclic by finding a group $G$ such that $|G|=N$ that cannot be generated by only $1$ element. Consider the group $G=\mathbb{Z}/p\mathbb{Z}\times\mathbb{Z}/Kp\mathbb{Z}$. For any element $g=(a,b)\in G$, $a$ will have an order $O_1|p$, and $b$ will have order $O_2|Kp$. Then, $\mathrm{ord}(g)=[O_1, O_2]|Kp$. Therefore, the subgroup $H_g\le G$ generated by $g$ must have at most $Kp$ elements, so $H_g\neq G$ for all elements $g$. Thus, $G$ cannot be generated by only $1$ element.

All of the prime numbers and $1$ are cyclic: The group with $1$ element is just the trivial group, which can be generated without any generators, so it is clearly cyclic. Then, consider a group $G$ with $|G|=p$, where $p$ is a prime. The identity will have order $1$, but every other element $g\in G$ must have order $p$. From this, we can show that $G\cong\mathbb{Z}/p\mathbb{Z}$. The group $\mathbb{Z}/p\mathbb{Z}$ is obviously cyclic, since it can be generated by the element $1$ (in fact, it can be generated by any nonzero element).

So what is the general rule? It turns out that it is not at all obvious. What do you think the answer might be?

It turns out that the necessary and sufficient condition is the following:

A positive integer $n$ is cyclic if and only if $(n,\phi(n))=1$.

We will prove the "only if" direction and leave the "if" direction without proof. If you are interested in a full proof, you can go to this article by Joseph A. Gallian and David Moulton.

We have already proved above that a cyclic number must be squarefree. Suppose that we have a number that is a product of distinct primes, i.e. $n=p_1p_2...p_k$. Then, $\phi(n)=(p_1-1)(p_2-1)...(p_k-1)$. Then, if $(n,\phi(n))\gt 1$, then $n$ has prime divisors $p, q$ such that $q<p$ and $q|(p-1)$. Since $(\mathbb{Z}/p\mathbb{Z})^\times$ (i.e. $\mathbb{Z}/p\mathbb{Z}$ excluding the element $0$) is a group under multiplication of order $(p-1)$, there exists an element $s\in(\mathbb{Z}/p\mathbb{Z})^\times$ such that $\mathrm{ord}(s)=q$. Consider the group $H=<a,b|a^q=b^p=e, aba^{-1}=b^s>$. Then, $H$ is a non-abelian group of order $pq$, and it follows that $H\times \mathbb{Z}/\frac{n}{pq}\mathbb{Z}$ is a non-abelian group of order $n$, meaning that it cannot be cyclic. Therefore, if $(n,\phi(n))\gt 1$, then $n$ is not cyclic.