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

Question

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.

Answer 1

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 $.

Answer 2

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)