$\psi (m)\leq \phi (m)$ or $\psi (m) \geq \phi (m)$ when $\psi (m)\neq 0$?

Question

(This is different than If $x^m=e$ has at most $m$ solutions for any $m\in \mathbb{N}$, then $G$ is cyclic)
I was trying to solve this:

Let $G$ be a finite abelian group of order $n$ for which the number of solutions of $x^m=e$ is at most $m$ for any $m$ dividing $n$. Prove that $G$ must be cyclic. [Hint:Let $\psi (m)$ be the number of elements in $G$ of order $m$. Show that $\psi (m)\leq \phi (m)$, and use $n=\Sigma_{m\mid n}\phi (m) $]

What I have proven is that $\Sigma_{d|n}(ψ(d)−ϕ(d))=0$, then if the statement in the hint holds, ψ(d)=ϕ(d) for every d|n. n divides itself, therefore, $\psi (n)=ϕ(n)≠0$. Therefore G admits a generator, and we'll be done.The problem is to prove the statement in the hint. Yet I have conluded a different seemingly contradictory result, which doesn't help solve the problem at all, since it could be that $ψ(n)=0,ψ(n)−ψ(d)<0$ and $ψ(d)−ϕ(d)>0$ for some $d≠n$. Of course I don't know how to show that $\psi (m)\leq \phi (m)$, and here is how I got this contradiction:
If $\psi (m)\neq 0$, then let $m\neq 1,m\mid n$. Consider an element $a\in G,|a|=m$. Within its cyclic group, there will be $\phi (m)$ elements with order $m$ since any element $a^i$ in it is a generator if and only if $\gcd(m,i)=1$. Therefore $\psi(m) \geq \phi (m)$ since some element out side the cyclic group may have order $m$ too.
If this reasoning is correct, I think it will contradict with the fact in the hint which is $\phi(m) \geq \phi(m)$. The number of solutions is $\Sigma_{d|m}\psi (d)$, which is always greater than $\psi (m)$. So no matter how great $\psi (m)$ is, or how $\psi (m) >\phi (m)$, the number of solution may still be less than $m$. What's going wrong? How to prove the statment in the hint? Help me please. Also I have read through If $x^m=e$ has at most $m$ solutions for any $m\in \mathbb{N}$, then $G$ is cyclic, but for the accepted answer, it doesn't show how to prove the fact in the hint, and other answers do not use the fact in the hint.

Answer 1

Let $d\mid n$ and suppose that $g\in G$ has order $d$. Then $$1,g,g^2,\ldots,g^{d-1}$$ are all different, and are solutions of the equation $x^d=e$ in $G$. We have exhibited $d$ solutions of the equation, and so by assumption there are no further solutions. Moreover, not all the powers $g^k$ have order $d$, as some will have smaller order. In fact, $g^k$ has order $d$ if and only if $k$ is relatively prime to $d$, and so the number of elements of order $d$ is $\phi(d)$, and we have $\psi(d)=\phi(d)$. This argument rests on the assumption that there is some element of order $d$; but if there is not then $\psi(d)=0$, and certainly in either case we have $\psi(d)\le\phi(d)$.

Answer 2

I have an answer, but it uses more knowledge than I think we want to. In particular, it comes close to using the structure theorem for finite abelian groups.

I claim that for any finite abelian group $G$ of order $n$ and any $m|n$, there is a subgroup $H \leq G$ of order $m$. If you can accept this, I can provide a proof. I don't like that I have to assume this. Write $\psi_H(d)$ for the number of elements of $H$ of order exactly $d$.

The assumption on $G$ can be rephrased as $m \geq \sum_{d|m} \psi(m)$; an element $x$ has $x^m = e$ just if its exact order divides $m$.

Given an $H \leq G$ of order $m$, every element is of order dividing $m$, so one has $$\sum_{d|m} \psi_H(d) = m = \sum_{d|m} \phi(d).$$ Since $\psi(d) = \psi_G(d) \geq \psi_H(d)$, one has for all $m|n$ that $$\sum_{d|m} \psi_G(d) \geq \sum_{d|m} \phi(d).$$

Also, if there is any element of order $m$, then there are at least $\phi(m)$ elements of order $m$, so $|T_m| = \psi(m) \geq \phi(m)$ for all $m|n$ such that $T_m \neq \emptyset$.

Note that $A_1 = \{e\}$, and $\psi(1) = \phi(1) = 1$.

Let $m | n$. Inductively assume that for all $d$ properly dividing $m$, we have $\psi(d) = \phi(d)$.

By assumption, $$\sum_{d|m} \phi(d) = m \geq \sum_{d|m} \psi(d).$$ Separating out the terms $\phi(m)$ and $\psi(m)$, one gets $$\phi(m) + \sum_{d|m\ \&\ d \neq m} \phi(d) \geq \psi(m) + \sum_{d|m\ \&\ d \neq m} \psi(d). $$ By the inductive assumption, the sums are equal, so $\phi(m) \geq \psi(m)$. But if $\psi(m)$ were 0, since for all $d|m$ we have $\phi(m) = \psi(m)$, we couldn't have $\sum_{d|m} \psi(d) \geq \sum_{d|m} \phi(d)$, so $\psi(m) \neq 0$ and hence $\psi(m) = \phi(m)$, concluding the induction.

Obviously this is horrible, but I don't see another way to complete the induction. We know that the entire sums $\sum_{d|n} \phi(d)$ and $\sum_{d|n} \psi(d)$ are equal (both must equal $n$), but I don't see how to use this as an inductive step without leveraging some of the structure theory of abelian groups or $p$-Sylow groups.