•

Main

Intuitive version

Cauchy's theorem on subgroup existence: intuitive version

Discussion0

Written by Patrick Stevens last updated 30th Jun 2016

Title

Tab title

Tab subtitle

Cauchy's Theorem states that if

G

is a finite group, and is a prime dividing the order of , then has an element of order . Equivalently, it has a subgroup of order .

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 for its identity. We will try and find an element of order .

What does it mean for an element

x \neq e

to have order ? Nothing more nor less than that . (This is true because is prime; if were not prime, we would additionally have to stipulate that is not for any smaller .)

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 and the group elements are with the identity, then and are two different such combinations. Then has order if and only if the combination multiplies out to give .

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 multiplies to give , it makes sense only to consider the combinations which multiply out to give in the first place. So, for instance, we will exclude the tuple from consideration if it is the case that is the identity (equivalently, that ). For convenience, we will label the set of all the allowed combinations: let us call it .

Of the tuples in

X

, we are looking for one with a very specific property: every entry is equal. For example, the tuple is no use to us, because it doesn't tell us an element such that ; it only tells us that . So we will be done if we can find a tuple in 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

: it is , since every element of is determined exactly by its first places (after which the last is fixed). There are no restrictions on the first places, though: we can find a th element to complete any collection of .

Example

p=5

, and we have the first four elements , then we know the fifth element must be . Indeed, , and inverse elements of a group are unique, so nothing else can fill the last slot.

So we have

, of size ; we have that divides (and so it divides ); and we also have an element of . But notice that if is in , then so is ; and so on through all the rotations of an element. We can actually group up the elements of 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 . But if the bucket contains any tuple which is not "the same element repeated times", then there must be exactly things in the bucket: namely the things we get by rotating . (Exercise: verify this!)

Show solution

The bucket certainly does contain every rotation of

: 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 , because two tuples are in the bucket if and only if we can rotate one to get the other; equivalently, is in the bucket if and only if we can rotate it to get .

How many such rotations are there? We claimed that there were

of them. Indeed, the rotations are precisely

and there are

of those; are they all distinct? Yes, they are, and this is because is prime (it fails when , for instance, because can be rotated four places to give itself). Indeed, if we could rotate the tuple nontrivially (that is, strictly between and times) to get itself, then the integer , the "number of places we rotated", must divide the integer "length of the tuple".

Todo

explain this better

But that tells us that

divides the prime , so is or itself, and so either the tuple is actually "the same element repeated times" (in the case ) ^[1], or the rotation was the "stupid" rotation by places (in the case ).

OK, so our buckets are of size

exactly, or size exactly. We're dividing up the members of - that is, things - into buckets of these size; and we already have one bucket of size , namely . But if there were no more buckets of size , then we would have dividing 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 , the total must be divisible by , since each individual bucket was ^[2]; so is divisible by . But that is a contradiction, since is also divisible by .

So there is another bucket of size

. A bucket of size contains something of the form : that is, it has shown us an element of order .

Summaries

There are no custom summaries written for this page, so users will see an excerpt from the beginning of the page when hovering over links to this page. You can create up to 3 custom summaries; by default you should avoid creating more than one summary unless the subject matter benefits substantially from multiple kinds of explanation.

Cauchy's Theorem states that if 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$ .

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 \neq 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 \neq 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 $e e a b a$ is the identity (equivalently, that $a b a = 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 $a b c b b = 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$ .

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, $a a b e (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!)

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

But that tells us that

n

divides the prime

p

, so

n

1

p

itself, and so either the tuple is actually "the same element repeated

p

times" (in the case

n = 1

) ^[1], 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 ^[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$ .

^{^︎}
But we're only considering $T$ which is not of this form!
^{^︎}
Compare with the fact that the sum of even numbers is always even; that is the case that $p = 2$ .

Parents:

Cauchy's theorem on subgroup existence