Show that $G$ is cyclic Here is a problem from Herstein.

Let G be a finite abelian group so that the equation $x^n=e$ has at most $n$ solutions in $G$ for every positive integer $n$. Show that $G$ is cyclic.

I will have to basically show that there exists an element $g$ in $G$ having order $o(G)$. 
I showed that such an element exists if $o(G)=p_1p_2...p_k$ where $p_i$ are primes. But I could not proceed if $o(G)=p_1^{a_1}p_2^{a_2}$. I feel that if I can prove this I will be able to extend.
 A: Hint.
If $G$ is not cyclic, then there exists a prime $p$ and a subgroup of $G$ isomorphic to $C \times C$, where $C$ is cyclic of order $p$.
Then the equation $$x^p=e$$ has at least $p^2$ solutions: the elements of $C \times C$.
A: Every element of $G$ has "some" finite order.
Furthermore, if $o(x) = d$, then $d|o(G)$.
Let the various orders of elements of $G$ be $d_1,d_2,\dots,d_k$ (these are all divisors of $o(G)$).
Let $S_{d_j}$ denote the subset of $G$ which consists of elements of order $d_j$.
Then $o(G) = \sum_j|S_{d_j}|$.
Suppose $x \in S_{d_j}$. Then $\langle x\rangle$ accounts for at least $\phi(d_j)$ elements of $S_{d_j}$ (here $\phi$ is the Euler totient function).
However, since every element $y$ of $\langle x\rangle$ satisfies $y^{d_j} = e$, and $\langle x\rangle$ has $d_j$ elements, $\langle x\rangle$ already contains ALL the elements of order $d_j$.
Thus we find that $|S_{d_j}| = \phi(d_j)$.
Now if $o(G) = m$, it is known that:
$m = \sum\limits_{d|m} \phi(d)$.
Note this sum includes $d = m$.
But if all the orders $d_1,\dots,d_k$ are less than $m$, we have:
$o(G) = \sum_j |S_{d_j}| = \sum_j \phi(d_j) < o(G)$, a contradiction.
Hence $G$ has an element of order $m$, and is thus cyclic.
EDIT: let me be a little clearer on how this proof works, by using the example $|G| = 12$.
If we have an element of order $12$, we are done, $|G|$ is cyclic. So assume not. How many elements of order $6$ can we have? If we have $1$, call it $a$, then $\langle a\rangle$ is a cyclic subgroup of $G$ of order $6$. This gives us $6$ solutions to $x^6 = e$, namely: $e,a,a^2,a^3,a^4,a^5$. By our assumption on $G$ this is the MOST we can have, for if $y \not\in \langle a\rangle$, and $y$ has order $6$, we have at least $7$ solutions to $x^6 = e$.
But this gives us (at most) $2$ elements of order $6$ (namely: $a$ and $a^5$), so if we have an element of order $6$, we have at most $2$. We know the identity (and only the identity) has order $1$, so we have at least $9$ elements unaccounted for.
A similar investigation shows we can at most have $2 = \phi(4)$ elements of order $4$, and $2$ elements of order $3$, and but a single element of order $2$.
So the total number of elements of orders $1,2,3,4$ and $6$ is at most:
$1 + 1 + 2 + 2 + 2 = 8 < 12$.
The remaining $4$ elements must be of order $12$, so our original assumption that $G$ is non-cyclic is impossible.
Note that the assumption that $G$ be abelian is unnecessary. The given condition already implies $G$ has ONLY one (at most) subgroup of order $d$, where $d|o(G)$, and since $G$ is finite, adding up the orders of such subgroups (when they exist) shows we need each and every one of them to "fill up $G$", that is-we have exactly one of each subgroup of order $d$, for EVERY divisor of $o(G)$.
In other words, the Euler totient function serves as a kind of "accountant", keeping track of the total number of positive integers removing multiples (which in this case correspond to the "powers" of elements) leaves behind. It is exceedingly precise in this regard.
A: You can proceed by induction. So you may suppose that every proper subgroup of $G$ is cyclic. If $n$ is a prime power $p^{a}$, then there are at most $p^{a-1}$ solutions of $x^{p^{a-1}} =1$, so there is at least one solution of $x^{p^{a}} =1 \neq x^{p^{a-1}}$ in $G$, and $G$ is cyclic.
If $n$ is not a prime power, then write $n = p_{1}^{a_{1}} \ldots p_{k}^{a_{k}}$ where the $p_{i}$ are distinct primes. By induction, for each $i$, $G$ contains an element $x_{i}$ of order $p_{i}^{a_{i}}$ for each $i$. Then $x_{1}x_{2} \ldots x_{k}$ has order $n$.
