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

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

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!)

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”. 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$$) <div><div>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 noteCompare 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$$.

Parents: