a repository of mathematical know-how

To prove facts about finite groups, use induction on the order

Quick description

One approach to proving results about finite groups is by using induction on the order of the group. The general idea is that one has many constructions of subgroups, such as the formation of the centre, or of centralizers of elements, or of normalizers of subgroups, to which one can hope to apply an inductive argument.


Basic group theory.

Note iconIncomplete This article is incomplete. More examples wanted

Example 1

Cauchy's theorem states that if a prime p divides the order of a finite group G, then G contains an element of order p. We present a proof of Cauchy's theorem via induction on the order of G. (Many other proofs are possible; a simple proof using an approach via group actions is here.)

We first consider the decomposition of G into conjugacy classes. If g is any element of G, then the stablizer of G under the action of G via conjugation is equal to C_G(g), the centralizer of g in G. Thus the number of conjugates of g is equal to the index C_G(g)], and so if \{g_1,\ldots,g_n\} is a set of conjugacy class representatives of G, then


Note that C_G(g)] = 1 if and only if C_G(g) = G, or equivalently, if and only if g lies in the centre Z of G. Thus if we label our conjugacy class representatives so that the first m representatives are the elements of the centre, then we may rewrite the above equation in the form


where the sum is over the non-central conjugacy class representatives, i.e. over those conjugacy class representatives whose conjugacy class contains more than one element. (This formula is known as the class equation.)

Now suppose that p does not divide C_G(g_i)] for some i = m+1,\ldots,n. Then since p does divide |G|, we find that p divides the order C_G(g_i). Since g_i is not central in G (by assumption), we find that C_G(g_i) is a proper subgroup of G. Thus, by induction, we may conclude that C_G(g_i) contains an element of order p. Since C_G(g_i) is a subgroup of G, we also get an element of order p in G, and so are done.

It remains to consider the case when p divides C_G(g_i)] for all i  = m+1,\ldots,n. Since p divides the order of |G|, we then conclude from the class equation that p divides |Z|. Since Z is an abelian group, this reduces Cauchy's theorem for a general finite group to the case of a finite abelian group.

Cauchy's theorem for finite abelian groups follows immediately from the fundamental theorem of finite abelian groups. However, we can also prove it directly, using the same strategy of induction on the order.

Thus suppose that A is a finite abelian group, and that p is a prime dividing |A|. Let a be any non-identity element of A, and let B be the subgroup of A generated by a. The order of B is equal to the order of a, which we denote by r. If p divides r, then a^{r/p} is an element of B, and hence of A, of order p, and we are done.

If p does not divide the order of B, then we form the quotient A/B. (It is here that we use the fact that A is abelian, so as to be certain that its subgroup B is normal.) Since a was chosen to be non-trivial, the order of A/B is less than the order of A, and since p does not divide the order of B by assumption, it must divide the order of A/B. By induction, we conclude that A/B must have an element of order p, say \overline{a}. Let a' \in A be a preimage of \overline{a} under the natural projection A \rightarrow A/B (or, if you prefer, a representative of the coset \overline{a}). Since the image \overline{a} of a' in A/B has order p, the order of a' must be divisible by p. Thus, if we let r' denote this order, the element a^{r'/p} of A has order p. This completes the proof of Cauchy's theorem in the abelian case.


A quick comment: I see that

A quick comment: I see that you put the group theory front page as the parent for this article, but that you didn't put a link in that article. I point this out in case you were expecting that link to be added automatically, since that does not happen. I've added the link myself now.

Two minor comments. First,

Two minor comments. First, the parent of this article should perhaps now be changed to "How to solve problems about finite groups". Secondly, this article itself could easily have its title made imperative if one omitted "How to". I think that would be an improvement. Or perhaps better would be "To prove facts about finite groups, use induction on the order". To the objection, "But there are many problems for which that does not work," I would say that I see Tricki titles as a bit like sellers in a busy market: lots of people are shouting out, trying to persuade you to buy their products, and you are not expected to obey them all.

I changed the title following

I changed the title following the second of your suggestions.

Post new comment

(Note: commenting is not possible on this snapshot.)

Before posting from this form, please consider whether it would be more appropriate to make an inline comment using the Turn commenting on link near the bottom of the window. (Simply click the link, move the cursor over the article, and click on the piece of text on which you want to comment.)