Help to prove that $U_{p}$ is a cyclic group.

As part of my study of Abstract Algebra, I’m trying to prove that $U_{p}$ is cyclic for $p$ a prime number. It’s a classical result, but I’m trying to prove it following four steps stated as problems in a book. I was able to handle Problems $1$ and $2$, but $3$ is giving me trouble.

Problem $3$. Let $G$ be a finite abelian group of order $n$ for which the number of solutions of the equation $x^{m} = e_{G}$ is at most $m$ for any $m$ dividing $n$. Prove that $G$ must be cyclic.

Hint: Let $\psi(m)$ be the number of elements of $G$ of order $m$. Show that $\psi(m) \leq \phi(m)$ and use Problem $2$. ($\phi$ is Euler’s totient function.)

The other two problems are:

Problem $1$. In a cyclic group of order $n$, show that for each positive integer $m$ that divides $n$, there are $\phi(m)$ elements of order $m$.

Problem $2$. Using Problem $1$, show that $\displaystyle n = \sum_{m|n} \phi(m)$.

I sincerely have no clue on how to solve, or merely attack, Problem $3$, so I came here looking for a better hint. I’m supposed to use only basic group-theoretic results up to Lagrange’s Theorem.

Note: It’s not homework, just personal study. The book is I. N. Herstein’s Abstract Algebra.

• did you show that $\psi(m)\leq \varphi(m)$? Commented Apr 26, 2015 at 19:50

Here is a proof without contradiction.

Let $m$ be a factor of $n = |G|$, and define $$A_{m} \stackrel{\text{df}}{=} \{ x \in G \mid {\text{ord}_{G}}(x) = m \}.$$ Then $\psi(m) = |A_{m}|$ according to the definition of $\psi$. We now have two cases:

Case 1: $A_{m} = \varnothing$.

In this case, $\psi(m) = 0$, so $\psi(m) \leq \phi(m)$.

Case 2: $A_{m} \neq \varnothing$.

Let $g \in A_{m}$. Then $g^{1},\ldots,g^{m}$ are distinct elements of $G$. They are also solutions of $x^{m} = e$, and so by the requirement imposed by the problem, they are all of the solutions. It remains to figure out which of them have order $m$.

Choose a $k \in \{ 1,\ldots,m \}$.

• If $\gcd(k,m) = 1$, then ${\text{ord}_{G}}(g^{k}) = m$. To prove this, let $l = {\text{ord}_{G}}(g^{k})$. Then $m | k l$, and as $\gcd(k,m) = 1$, we have $m | l$. However, $(g^{k})^{m} = (g^{m})^{k} = e$, so $l = m$.
• If $\gcd(k,m) = d > 1$, then $\dfrac{k}{d}$ and $\dfrac{m}{d}$ are both positive integers, and $\dfrac{m}{d} < m$. As $$(g^{k})^{\frac{m}{d}} = (g^{m})^{\frac{k}{d}} = e,$$ it follows that ${\text{ord}_{G}}(g^{k}) < m$.

Therefore, only $\phi(m)$ elements of $G$ have order $m$, and so $\psi(m) = \phi(m)$.

Conclusion: $\psi(m) \leq \phi(m)$ for each factor $m$ of $n$.

Elaqqad has shown above that $\psi(m) = \phi(m)$ for each factor $m$ on $n$. In order to prove that $G$ is cyclic, observe that because $\psi(n) = \phi(n) \geq 1$, there exists an element of order $n$, which is then a cyclic generator of $G$.

• Maybe it is a silly question, but, where is used that $G$ is abelian? or it is not needed at all? The same for Eleqqad's solution. Commented Apr 30, 2015 at 15:23
• @xndrme: It seems that we don’t need the abelian hypothesis and that it’s a part of the conclusion. Commented Apr 30, 2015 at 19:00

For the hint By contradiction assume that there exists $k$ such that $\psi(k)> \phi(k)$, take $a$ one element of order $k$, the elements of order $k$ of the form $a^i$ are those of the form $a^i$ with $\gcd(i,k)=1$ and there is only $\varphi(k)$ elements of order $k$ of this form,but there exists $\psi(k)>\varphi(k)$ elements of order $k$, so there exists an element of order $k$ which is not of the form $a^i$ call it $b$ hence the equation $x^k=1$ have more than $k$ solutions which are $e,a,\cdots, a^{k-1},b$. Contradiction.

To conclude we have $\psi(m)\leq \varphi(m)$ for every $m$ and hence: $$n=\sum_{d|n}\psi(d)\leq \sum_{d|n}\varphi(d)=n \tag 1$$ which gives you that $\psi(n)=\varphi(n)$ (if it's not the inequality $(1)$ becomes strict $n<n$ not possible)