# Cauchy's theorem on subgroup existence: intuitive version

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$.