Finite group for which $|\{x:x^m=e\}|\leq m$ for all $m$ is cyclic. 
Let $G$ be a finite group. For each positive integer $m$, if $x^{m}=e$ has at most $m$ solutions in $G$, $G$ is cyclic.

What I have thought is that $n=\sum_{d\mid n}\phi(d)$ can be used to solve this and showing that $|G|$ order element in $G$ exists is enough. 
 A: Here's a different proof that uses Sylow's theorems. Suppose that $x^m = e$ has at most $m$ solutions in $G$ for all positive integers $m$.
Then for every prime $p$ dividing $|G|$, there exists at most one Sylow $p$-subgroup. Otherwise we would find more than $p^{\alpha}$ solutions to $x^{p^{\alpha}} = e$, where $p^\alpha$ is the largest power of $p$ dividing $|G|$. The Sylow $p$-subgroup is cyclic, since $x^{p^{\alpha-1}} = e$ has less than $p^\alpha$ solutions, so there exists an element $g$ satisfying $g^{p^\alpha} = e$ and $g^{p^{\alpha-1}} \neq e$.
Because every Sylow $p$-subgroup of $G$ is normal and cyclic, the group $G$ is cyclic.
There is a stronger statement due to Cohn, see the following paper (PDF link).

J. H. E. Cohn, A condition for a finite group to be cyclic, Proc. Amer.
  Math. Soc., Vol. 32, No. 1 (1972).

In this article (it is short, and the proof is simple counting argument) Cohn proves that a finite group $G$ is cyclic if for every prime power $p^k$, the equation $x^{p^k} = e$ has at most $p^{k+1} - 1$ solutions.
A: Yes, that is perfect. Let $|G|=n$. Note that
$$G=\bigsqcup_{d\mid n}X_d$$
where $X_d$ is the set of elements of $G$ of order $d$. Now, if we can show that our restriction requires $\#(X_d)\leqslant \phi(d)$ then the equality $\displaystyle n=\sum_{d\mid n}\phi(d)$ will actually force $\#(X_d)=\phi(d)$, for all $d\mid n$, and so, in particular $\#(X_n)>0$. 
Now, suppose that there were more than $\phi(d)$ elements of $G$ of order $d$. Note then that since the cyclic group $\langle x\rangle$, for any $x\in X_d$, has exactly $\phi(d)$ elements of order $d$, there must exist another element $y\in G$ with $|y|=d$ and $y\notin \langle x\rangle$. But, Lagrange's theorem then implies that we've produced $|\langle x\rangle|+1=d+1$ solutions to $x^d=1$--contradictory to assumption. 
A: Here's a very basic counting argument.
Let $|G| = n = \prod_{i=1}^k\,p_i^{q_i}$, where the $p_i$ are distinct primes and the $q_i$ are $\geq 1$.
By Lagrange's Theorem, the order of each element must divide $n$.
Hence, if $G$ were not cyclic, there would be no element of order $n$ and we would have $2n$ equals
\begin{align}
&\sum_{0\leq l_k\leq q_k}\,\sum_{0\leq l_{k-1}\leq q_{k-1}}\,\dots\,
\sum_{0\leq l_2\leq q_2}\,\sum_{0\leq l_1\leq q_1}\,\left|\left\{g\in G\,\middle |\, o(g) = \prod_{i=1}^k\,p_i^{l_i}\right\}\right|
\\\leq\,\,\,&
\sum_{0\leq l_k\leq q_k}\,\sum_{0\leq l_{k-1}\leq q_{k-1}}\,\dots\,
\sum_{0\leq l_2\leq q_2}\,\sum_{0\leq l_1\leq q_1}\,\left|\left\{g\in G\,\middle |\, g^{\prod_{i=1}^k\,p_i^{l_i}}=e\right\}\right|
\\\leq\,\,\,&
\sum_{0\leq l_k\leq q_k}\,\sum_{0\leq l_{k-1}\leq q_{k-1}}\,\dots\,
\sum_{0\leq l_2\leq q_2}\,\sum_{0\leq l_1\leq q_1}\,\prod_{i=1}^k\,p_i^{l_i}
\\=\,\,\,&
\sum_{0\leq l_k\leq q_k}\,p_k^{l_k}\left(
\sum_{0\leq l_{k-1}\leq q_{k-1}}\,p_{k-1}^{l_{k-1}} \left(
\dots\,\left(
\sum_{0\leq l_2\leq q_2}\, p_2^{l_2}\,
\left(\frac{p_1^{q_1+1}-1}{p_1-1}\right)
\right)\right)\dots\right)
\\=\,\,\,&\left(\frac{p_1^{q_1+1}-1}{p_1-1}\right)\cdot
\sum_{0\leq l_k\leq q_k}\,p_k^{l_k}\left(
\sum_{0\leq l_{k-1}\leq q_{k-1}}\,p_{k-1}^{l_{k-1}} \left(
\dots\,\left(
\sum_{0\leq l_2\leq q_2}\, p_2^{l_2}\,
\right)\right)\dots\right)
\\=\,\,\,&\dots
\\=\,\,\,&\prod_{i=1}^k\frac{p_i^{q_i+1}-1}{p_i-1}.
\end{align}
However:
$$2n = \prod_{i=1}^k\,2p_i^{q_i} > \prod_{i=1}^k\frac{p_i^{q_i+1}-1}{p_i-1}.$$
Indeed, because $p_i$ is prime and hence $\geq 2$, we have that $2p_i^{q_i} > \frac{p_i^{q_i+1}-1}{p_i-1} \iff p_i^{q_i+1}+1>2p_i^{q_i}$.
