Group of units mod n is cyclic

page=82, problems 37 to 40

The set of all positive integers less than a given positive integer $n$ and co-prime to $n$ form a group under multiplication modulo $n$, which is denoted by $U_n$. Note that $U_n$ in general can have any group structure: $U_6\cong C_3$, $U_8\cong V_4$, $U_{10}\cong C_4$, $U_{15}\cong C_2\times C_4$, etc. However, we will prove that when $n$ is prime (denoted by replacing $n$ with $p$), $U_p$ is cyclic.

Theorem 1(Theorem).

In a cyclic group $G$ of order $n$, for each positive integer $m$ that divides $n$, there are $\varphi (m)$ elements of order $m$.

For $m=n$, we know that there are $\varphi (n)$ elements of order $n$. Now, for $m\ne n$, the elements of order $m$ must lie in a subgroup of $G$ of order $m$. Note that in cyclic groups, only one group of order $m$ exists, so all the elements of order $m$ in $G$ must lie in this one subgroup. This subgroup would have $\varphi (m)$ elements of order $m$.

It follows that $n={\sum }_{m|n}\varphi (m)$ (note that this is a general result which can be interpreted without any group theory).

---

Unrelated thing i proved that didn’t turn out to be useful here but is nonetheless interesting:

Theorem 2(Theorem).

For any group $G$ of order $n$, let the number of elements of order $m$ be denoted by $\psi (m)$. Then, $\psi (m)=k\varphi (m),k\in {\mathbb{Z}}_{\ge 0}$.

If there are no elements of order $m$, $k=0$.
Let $x$ be an element of order $m$. $x$ must generate a subgroup of $G$ of order $m$, which in turn must have $\varphi (m)$ elements of order $m$. Thus, the moment we have one element of order $m$, $\varphi (m)$ elements of order $m$ are forced onto us. Let $y$ be another element of order $m$ such that $⟨y⟩\ne ⟨x⟩$. The intersection $⟨y⟩\cap ⟨x⟩$ must be a proper subgroup of $⟨y⟩$ and $⟨x⟩$, and so must have order less than $m$, preventing it from housing any elements of order $m$. Thus, the $\varphi (m)$ elements of order $m$ in $⟨y⟩$ are different from the ones in $⟨x⟩$, bringing the total count to $2\varphi (m)$, and you get the idea.

---

Theorem 3(Theorem).

Let $G$ be a finite group of order $n$ for which the number of solutions of $x^m=e$ is at most $m$ for any $m$ dividing $n$. Then, $G$ must be cyclic.

As shown above, having one element of order $m$ results in having an entire cyclic subgroup $A_m$ of order $m$. Not all elements in this cyclic subgroup will have order $m$, BUT, all elements in $A_m$ will satisfy $x^m=e$, since all their orders divide $m$. This gives us $m$ solutions to $x^m=e$, and $\varphi (m)$ elements of order $m$. If there exists another element of order $m$, then it must also satisfy $x^m=e$, bringing the number of solutions to $x^m=e$ to $m+1$. Thus, $\psi (m)\le \varphi (m)$. Now,

$$n=\sum _{m|n}\psi (m)\le \sum _{m|n}\varphi (m)=n$$

Thus, $\psi (m)=\varphi (m)$ for all $m|n$.
w