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.
Best Answer
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 \} $.
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 $.