Cauchy's Theorem states that if $~$G$~$ is a finite [-group], and $~$p$~$ is a prime dividing the order of $~$G$~$, then $~$G$~$ has an element of order $~$p$~$. Equivalently, it has a subgroup of order $~$p$~$.

This theorem is very important as a partial converse to Lagrange's theorem: while Lagrange's theorem gives us restrictions on what subgroups can exist, Cauchy's theorem tells us that certain subgroups definitely do exist. In this direction, Cauchy's theorem is generalised by the [sylow_theorems_on_subgroup_existence Sylow theorems].

Proof

Let $~$G$~$ be a group, and write $~$e$~$ for its identity. We will try and find an element of order $~$p$~$.

What does it mean for an element $~$x \not = e$~$ to have order $~$p$~$? Nothing more nor less than that $~$x^p = e$~$. (This is true because $~$p$~$ is prime; if $~$p$~$ were not prime, we would additionally have to stipulate that $~$x^i$~$ is not $~$e$~$ for any smaller $~$i < p$~$.)

Now follows the magic step which casts the problem in the "correct" light.

Consider all possible combinations of $~$p$~$ elements from the group. For example, if $~$p=5$~$ and the group elements are $~$\{ a, b, c, d, e\}$~$ with $~$e$~$ the identity, then $~$(e, e, a, b, a)$~$ and $~$(e,a,b,a,e)$~$ are two different such combinations. Then $~$x \not = e$~$ has order $~$p$~$ if and only if the combination $~$(x, x, \dots, x)$~$ multiplies out to give $~$e$~$.

The rest of the proof will be simply following what this magic step has told us to do.

Since we want to find some $~$x$~$ where $~$(x, x, \dots, x)$~$ multiplies to give $~$e$~$, it makes sense only to consider the combinations which multiply out to give $~$e$~$ in the first place. So, for instance, we will exclude the tuple $~$(e, e, a, b, a)$~$ from consideration if it is the case that $~$eeaba$~$ is the identity (equivalently, that $~$aba = e$~$). For convenience, we will label the set of all the allowed combinations: let us call it $~$X$~$.

Of the tuples in $~$X$~$, we are looking for one with a very specific property: every entry is equal. For example, the tuple $~$(a,b,c,b,b)$~$ is no use to us, because it doesn't tell us an element $~$x$~$ such that $~$x^p = e$~$; it only tells us that $~$abcbb = e$~$. So we will be done if we can find a tuple in $~$X$~$ which has every element equal (and which is not the identity).

We don't really have anything to go on here, but it will surely help to know the size of $~$X$~$: it is $~$|G|^{p-1}$~$, since every element of $~$X$~$ is determined exactly by its first $~$p-1$~$ places (after which the last is fixed). There are no restrictions on the first $~$p-1$~$ places, though: we can find a $~$p$~$th element to complete any collection of $~$p-1$~$.

%%hidden(Example): If $~$p=5$~$, and we have the first four elements $~$(a, a, b, e, \cdot)$~$, then we know the fifth element must be $~$b^{-1} a^{-2}$~$. Indeed, $~$aabe(a^{-1} a^{-2}) = e$~$, and [ inverse elements of a group are unique], so nothing else can fill the last slot. %%

So we have $~$X$~$, of size $~$|G|^{p-1}$~$; we have that $~$p$~$ divides $~$|G|$~$ (and so it divides $~$|X|$~$); and we also have an element $~$(e,e,\dots,e)$~$ of $~$X$~$. But notice that if $~$(a_1, a_2, \dots, a_p)$~$ is in $~$X$~$, then so is $~$(a_2, a_3, \dots, a_p, a_1)$~$; and so on through all the rotations of an element. We can actually group up the elements of $~$X$~$ into buckets, where two tuples are in the same bucket if (and only if) one can be rotated to make the other.

How big is a bucket? If a bucket contains something of the form $~$(a, a, \dots, a)$~$, then of course that tuple can only be rotated to give one thing, so the bucket is of size $~$1$~$. But if the bucket contains any tuple $~$T$~$ which is not "the same element repeated $~$p$~$ times", then there must be exactly $~$p$~$ things in the bucket: namely the $~$p$~$ things we get by rotating $~$T$~$. (Exercise: verify this!)

%%hidden(Show solution): The bucket certainly does contain every rotation of $~$T$~$: we defined the bucket such that if a tuple is in the bucket, then so are all its rotations. Moreover, everything in the bucket is a rotation of $~$T$~$, because two tuples are in the bucket if and only if we can rotate one to get the other; equivalently, $~$A$~$ is in the bucket if and only if we can rotate it to get $~$T$~$.

How many such rotations are there? We claimed that there were $~$p$~$ of them. Indeed, the rotations are precisely $$~$(a_1, a_2, \dots, a_p), (a_2, a_3, \dots, a_p, a_1), \dots, (a_{p-1}, a_p, a_1, \dots, a_{p-2}), (a_p, a_1, a_2, \dots, a_{p-1})$~$$ and there are $~$p$~$ of those; are they all distinct? Yes, they are, and this is because $~$p$~$ is prime (it fails when $~$p=8$~$, for instance, because $~$(1,1,2,2,1,1,2,2)$~$ can be rotated four places to give itself). Indeed, if we could rotate the tuple $~$T$~$ nontrivially (that is, strictly between $~$1$~$ and $~$p$~$ times) to get itself, then the integer $~$n$~$, the "number of places we rotated", must divide the integer "length of the tuple". [todo: explain this better] But that tells us that $~$n$~$ divides the prime $~$p$~$, so $~$n$~$ is $~$1$~$ or $~$p$~$ itself, and so either the tuple is actually "the same element repeated $~$p$~$ times" (in the case $~$n=1$~$) %%note: But we're only considering $~$T$~$ which is not of this form!%%, or the rotation was the "stupid" rotation by $~$p$~$ places (in the case $~$n=p$~$). %%

OK, so our buckets are of size $~$p$~$ exactly, or size $~$1$~$ exactly. We're dividing up the members of $~$X$~$ - that is, $~$|G|^{p-1}$~$ things - into buckets of these size; and we already have one bucket of size $~$1$~$, namely $~$(e,e,\dots,e)$~$. But if there were no more buckets of size $~$1$~$, then we would have $~$p$~$ dividing $~$|G|^{p-1}$~$ and also dividing the size of all but one of the buckets. Mixing together all the other buckets to obtain an uber-bucket of size $~$|G|^{p-1} - 1$~$, the total must be divisible by $~$p$~$, since each individual bucket was %%note:Compare with the fact that the sum of even numbers is always even; that is the case that $~$p=2$~$.%%; so $~$|G|^{p-1} - 1$~$ is divisible by $~$p$~$. But that is a contradiction, since $~$|G|^{p-1}$~$ is also divisible by $~$p$~$.

So there is another bucket of size $~$1$~$. A bucket of size $~$1$~$ contains something of the form $~$(a,a,\dots,a)$~$: that is, it has shown us an element of order $~$p$~$.