Cauchy's theorem states that if $~$G$~$ is a finite Group and $~$p$~$ is a prime dividing $~$|G|$~$ the order of $~$G$~$, then $~$G$~$ has a subgroup of order $~$p$~$. Such a subgroup is necessarily cyclic (proof).

# Proof

The proof involves basically a single magic idea: from thin air, we pluck the definition of the following set.

Let $$~$X = \{ (x_1, x_2, \dots, x_p) : x_1 x_2 \dots x_p = e \}$~$$ the collection of $~$p$~$-[-tuple]s of elements of the group such that the group operation applied to the tuple yields the identity. Observe that $~$X$~$ is not empty, because it contains the tuple $~$(e, e, \dots, e)$~$.

Now, the cyclic group $~$C_p$~$ of order $~$p$~$ acts on $~$X$~$ as follows: $$~$(h, (x_1, \dots, x_p)) \mapsto (x_2, x_3, \dots, x_p, x_1)$~$$ where $~$h$~$ is the generator of $~$C_p$~$. So a general element $~$h^i$~$ acts on $~$X$~$ by sending $~$(x_1, \dots, x_p)$~$ to $~$(x_{i+1}, x_{i+2} , \dots, x_p, x_1, \dots, x_i)$~$.

This is indeed a group action (exercise).

%%hidden(Show solution):

- It certainly outputs elements of $~$X$~$, because if $~$x_1 x_2 \dots x_p = e$~$, then $$~$x_{i+1} x_{i+2} \dots x_p x_1 \dots x_i = (x_1 \dots x_i)^{-1} (x_1 \dots x_p) (x_1 \dots x_i) = (x_1 \dots x_i)^{-1} e (x_1 \dots x_i) = e$~$$
- The identity acts trivially on the set: since rotating a tuple round by $~$0$~$ places is the same as not permuting it at all.
- $~$(h^i h^j)(x_1, x_2, \dots, x_p) = h^i(h^j(x_1, x_2, \dots, x_p))$~$ because the left-hand side has performed $~$h^{i+j}$~$ which rotates by $~$i+j$~$ places, while the right-hand side has rotated by first $~$j$~$ and then $~$i$~$ places and hence $~$i+j$~$ in total. %%

Now, fix $~$\bar{x} = (x_1, \dots, x_p) \in X$~$.

By the Orbit-Stabiliser theorem, the orbit $~$\mathrm{Orb}_{C_p}(\bar{x})$~$ of $~$\bar{x}$~$ divides $~$|C_p| = p$~$, so (since $~$p$~$ is prime) it is either $~$1$~$ or $~$p$~$ for every $~$\bar{x} \in X$~$.

Now, what is the size of the set $~$X$~$? %%hidden(Show solution): It is $~$|G|^{p-1}$~$.

Indeed, a single $~$p$~$-tuple in $~$X$~$ is specified precisely by its first $~$p$~$ elements; then the final element is constrained to be $~$x_p = (x_1 \dots x_{p-1})^{-1}$~$. %%

Also, the orbits of $~$C_p$~$ acting on $~$X$~$ partition $~$X$~$ (proof). Since $~$p$~$ divides $~$|G|$~$, we must have $~$p$~$ dividing $~$|G|^{p-1} = |X|$~$. Therefore since $~$|\mathrm{Orb}_{C_p}((e, e, \dots, e))| = 1$~$, there must be at least $~$p-1$~$ other orbits of size $~$1$~$, because each orbit has size $~$p$~$ or $~$1$~$: if we had fewer than $~$p-1$~$ other orbits of size $~$1$~$, then there would be at least $~$1$~$ but strictly fewer than $~$p$~$ orbits of size $~$1$~$, and all the remaining orbits would have to be of size $~$p$~$, contradicting that $~$p \mid |X|$~$. [todo: picture of class equation]

Hence there is indeed another orbit of size $~$1$~$; say it is the singleton $~$\{ \bar{x} \}$~$ where $~$\bar{x} = (x_1, \dots, x_p)$~$.

Now $~$C_p$~$ acts by cycling $~$\bar{x}$~$ round, and we know that doing so does not change $~$\bar{x}$~$, so it must be the case that all the $~$x_i$~$ are equal; hence $~$(x, x, \dots, x) \in X$~$ and so $~$x^p = e$~$ by definition of $~$X$~$.