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

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

Solution 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)