Number of solutions to $x^n=e$ in group $G$ is divisible by $n$

This is precisely the Theorem of Frobenius.

Without representation theory, there is a proof, by induction; but more - it is double induction (on order of group and also on $n$). I didn't feel the proof elementary, so I am not writing proof here. But you may see following.

This theorem appears in very few standard books of Group Theory (Zassenhaus, M. Hall, Huppert, and no other books I saw giving group-theoretic proof).

However, a group-theoretic proof has been appeared in an interesting article in American Mathematical Monthly: http://www.maa.org/sites/default/files/3004416017467.pdf.bannered.pdf

The interesting things about this article is that it involves some niceapplications of it, and also gives all the sources of earlier known proofs.

Hope this would help! Let me know!