The question is like this: group $G$ has an order of $p^e*m$ for some prime $p$. ($m$ coprime $p$) Then G must contain an element g with the order of $p$ and $\# Cl(g)$ divides m.
Intuitively, there seems something to do with the Sylow theorem. However, after some trying, it's surely more than that.
The fact that $G$ has an element of order $p$ follows from Cauchy's Theorem, but we can do better: $G$ has a subgroup of order $p^e$, and we know that $p$-groups have nontrivial center. So $G$ has a subgroup $P$ of order $p^e$, and en element $g\in P$ of order $p$ and such that $g\in Z(P)$: $g$ commutes with every element of $P$.
Can you take it from here?