Cauchy's theorem

Theorem

Cauchy's theorem

T-060Home MU-204Threads structure

Statement

Let \(G\) be a finite group and let \(p\) be a prime number such that \(p \mid |G|\). Then \(G\) contains an element of order \(p\); equivalently, \(G\) has a subgroup isomorphic to \(\mathbb{Z}/p\mathbb{Z}\).

Why it matters

Cauchy's theorem is the bridge between the arithmetic of \(|G|\) (an integer, factorisable by elementary number theory) and the internal structure of \(G\) (a set with an operation). It is the base case on which the entire theory of Sylow subgroups is built: Sylow's first theorem, which guarantees a subgroup of order \(p^k\) for every prime power dividing \(|G|\), is proved by inducting from the single element that Cauchy's theorem supplies. Without it, one could not even guarantee that a group of order \(15\) contains an element of order \(3\), let alone classify it.

It also illustrates a technique of independent value — group actions used purely as a counting device (orbit-counting arguments), rather than to produce an explicit homomorphism or normal subgroup. The proof given below, due to J. H. McKay (1959), is a template for a whole family of arguments in combinatorial group theory.

Hypotheses

\(G\) is finite.For infinite groups the statement is false as stated: \((\mathbb{Q},+)\) is divisible and torsion-free, so it has no element of finite order at all, even though one might try to make sense of "\(p\) divides \(|G|\)" vacuously; more to the point \((\mathbb{R},+)\) has no element of order \(p\) for any prime \(p\) since it is torsion-free. Finiteness is what lets us count. \(p\) is prime.The composite analogue is false: \(G = \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}\) has order \(4\), and \(4 \mid |G|\), but \(G\) has no element of order \(4\) — every non-identity element has order \(2\). Primality is what forces the divisor lemma in Step 4 below to have only the two extreme cases. \(p \mid |G|\).If \(p \nmid |G|\) there is (generically) no element of order \(p\); e.g. \(G = \mathbb{Z}/6\mathbb{Z}\) has no element of order \(5\). This is not a subtle hypothesis but it is the entire content of the theorem: Lagrange's theorem already gives the converse-flavoured statement that the order of every element divides \(|G|\), so Cauchy's theorem is exactly the partial converse to Lagrange that survives for prime divisors.

Proof

We give McKay's counting proof. Write \(n = |G|\) and fix a prime \(p \mid n\).

X := \{(x_1, x_2, \ldots, x_p) \in G^p : x_1 x_2 \cdots x_p = e\}

Definition of the set we will count. This is a subset of the Cartesian power \(G^p\), cut out by the single equation that the ordered \(p\)-tuple multiplies to the identity. A

|X| = n^{p-1}

Choose \(x_1, \ldots, x_{p-1} \in G\) freely (that is \(n^{p-1}\) choices); the closing entry is then forced to be \(x_p = (x_1 x_2 \cdots x_{p-1})^{-1}\), which exists and is unique since \(G\) is a group. This is a bijection between \(X\) and \(G^{p-1}\), so \(|X| = n^{p-1}\). A

\text{cyclic rotation sends } X \text{ to } X

Define \(\sigma : G^p \to G^p\) by \(\sigma(x_1,\ldots,x_p) = (x_2,\ldots,x_p,x_1)\). We must check \(\sigma\) maps \(X\) into \(X\): if \(x_1 x_2 \cdots x_p = e\) then, conjugating by \(x_1\), \(x_1^{-1}(x_1x_2\cdots x_p)x_1 = x_1^{-1} e x_1\), i.e. \(x_2 x_3 \cdots x_p x_1 = e\). So the rotated tuple also lies in \(X\). Iterating, the cyclic group \(C_p = \langle \sigma \rangle\) of order \(p\) (generated by a single rotation, since rotating \(p\) times returns the original tuple) acts on \(X\) by repeated rotation. B

\text{every orbit of } C_p \text{ on } X \text{ has size } 1 \text{ or } p

By the Orbit–Stabiliser theorem, the size of the orbit of any \(x \in X\) equals \([C_p : \mathrm{Stab}(x)]\), which divides \(|C_p| = p\). Since \(p\) is prime its only positive divisors are \(1\) and \(p\); this is exactly where primality of \(p\) is used, and it is the step that fails for composite exponents. B

\text{an orbit has size } 1 \iff \text{ its tuple is constant}

The orbit of \((x_1,\ldots,x_p)\) has size \(1\) iff \(\sigma\) fixes it, i.e. \((x_2,\ldots,x_p,x_1) = (x_1,\ldots,x_p)\), which forces \(x_1 = x_2 = \cdots = x_p\). Conversely a constant tuple \((x,x,\ldots,x)\) is visibly fixed by rotation. So fixed points of the action correspond exactly to elements \(x \in G\) with \(x^p = e\) (since the tuple must also lie in \(X\), i.e. \(x^p = e\)). A

|X| \equiv |\mathrm{Fix}(C_p)| \pmod p

Partition \(X\) into \(C_p\)-orbits. By Step 4 each orbit contributes either \(1\) (mod \(p\), from a size-\(1\) orbit) or \(0\) (mod \(p\), from a size-\(p\) orbit) to \(|X|\). Summing over orbits, \(|X| = |\mathrm{Fix}(C_p)| + p \cdot (\text{number of size-}p\text{ orbits})\), which gives the congruence. This is the Cauchy–Frobenius / orbit-counting device applied mod \(p\) rather than the usual averaging over the whole group. C

|\mathrm{Fix}(C_p)| \equiv 0 \pmod p

Combine Steps 2 and 6: \(|X| = n^{p-1}\), and \(p \mid n\) by hypothesis, so \(p \mid n^{p-1}\) (as \(p-1 \ge 1\)), i.e. \(|X| \equiv 0 \pmod p\). Substituting into Step 6 gives \(|\mathrm{Fix}(C_p)| \equiv 0 \pmod p\). A

|\mathrm{Fix}(C_p)| \ge p

The tuple \((e,e,\ldots,e)\) lies in \(X\) (since \(e^p = e\)) and is constant, hence is a fixed point by Step 5; so \(|\mathrm{Fix}(C_p)| \ge 1\). But by Step 7 this count is a nonnegative multiple of \(p\); the only multiple of \(p\) that is \(\ge 1\) is itself \(\ge p\). Hence \(|\mathrm{Fix}(C_p)| \ge p\). B

\exists\, x \in G,\ x \ne e,\ x^p = e

By Step 5, fixed points correspond bijectively to elements \(x \in G\) with \(x^p = e\); Step 8 shows there are at least \(p \ge 2\) such elements, so at least one is not the identity. A

\mathrm{ord}(x) = p

Since \(x^p = e\), the order of \(x\) divides \(p\) (definition of order: the least positive \(k\) with \(x^k = e\) always divides any exponent that kills \(x\), by the division algorithm — write \(p = qk+r\), \(0 \le r \lt k\), then \(x^r = x^{p - qk} = e\) forces \(r = 0\) by minimality of \(k\)). As \(p\) is prime, its only divisors are \(1\) and \(p\); since \(x \ne e\) the order cannot be \(1\). Hence \(\mathrm{ord}(x) = p\), which is the element sought. \(\blacksquare\) A

Result

p \mid |G| \ \Longrightarrow\ \exists\, x \in G \text{ with } \mathrm{ord}(x) = p

Reading. Whenever a prime number divides the size of a finite group, that group is guaranteed to contain an element whose repeated self-multiplication cycles back to the identity after exactly \(p\) steps — equivalently, a copy of the cyclic group \(\mathbb{Z}/p\mathbb{Z}\) sits inside \(G\).

Scope. Applies to every finite group, abelian or not, for every prime \(p\) dividing \(|G|\); it says nothing about prime-power divisors \(p^k\) with \(k \ge 2\) (that refinement is Sylow's first theorem) and nothing about composite divisors of \(|G|\) in general.

Corollaries & converses

If \(|G| = p\) for a prime \(p\), then \(G\) is cyclic of order \(p\) (Cauchy gives an element of order \(p\); by Lagrange it generates all of \(G\)).
A finite group \(G\) is a \(p\)-group (every element has order a power of \(p\)) if and only if \(|G|\) is a power of \(p\) — the "only if" direction uses Cauchy's theorem applied to any other prime divisor to derive a contradiction.
Iterating Cauchy's theorem over the distinct prime factors of \(|G|\) shows every nontrivial finite group has at least one nontrivial proper subgroup unless \(|G|\) is prime.
The converse — "if \(G\) has an element of order \(p\) then \(p \mid |G|\)" — does hold, but it is just Lagrange's theorem in disguise and is much weaker; it gives no existence statement.
The naive converse-of-Lagrange, "for every divisor \(d\) of \(|G|\) there is a subgroup of order \(d\)", is false in general (e.g. \(A_4\), order \(12\), has no subgroup of order \(6\)); Cauchy's theorem is precisely the fragment of that false statement that survives when \(d\) is restricted to be prime.

Fails without

Finiteness dropped: \((\mathbb{R},+)\) or \((\mathbb{Q},+)\) are torsion-free groups — no non-identity element has finite order at all, so certainly none has order \(p\), regardless of any divisibility condition one tries to impose on a nonexistent "\(|G|\)".
Primality dropped (composite exponent): \(G = \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}\) (the Klein four-group) has order \(4\), and \(4 \mid |G|\), yet every non-identity element has order \(2\); there is no element of order \(4\). The proof breaks exactly at Step 4: with \(m=4\) composite, \(C_4\) can have orbits of size \(2\) on the analogous tuple set, so the mod-\(p\) counting collapses (\(2 \equiv 0 \pmod 2\) contaminates the argument).
Divisibility dropped: \(G = \mathbb{Z}/6\mathbb{Z}\) has order \(6\); \(5\) is prime but \(5 \nmid 6\), and indeed \(G\) has no element of order \(5\) (orders present are \(1,2,3,6\)). Step 2 would still give \(|X| = 6^{4}\), but Step 7 fails because \(5 \nmid 6^4\), so the fixed-point count need not be \(\equiv 0 \pmod 5\) and the argument gives no lower bound.

Common errors

Confusing Cauchy's theorem with Sylow's first theorem and asserting a subgroup of order \(p^k\) (for \(k \ge 2\)) exists whenever \(p^k \mid |G|\) — Cauchy only guarantees order exactly \(p\), one prime, not a full prime-power.
Trying to prove Cauchy's theorem for abelian groups by induction on \(|G|\) via a quotient \(G/H\), but forgetting that lifting an order-\(p\) element of \(G/H\) back to \(G\) does not automatically give order \(p\) in \(G\) — the lift's order need only be a multiple of \(p\), requiring a further power-raising step.
Asserting the converse of Lagrange's theorem in full ("every divisor of \(|G|\) is the order of some subgroup") using Cauchy's theorem as if it covered composite divisors too; it only covers prime divisors.
In the McKay proof, forgetting to check that the rotation map actually preserves the constraint set \(X\) (Step 3) and treating the action as "obviously" well-defined without the conjugation computation.
Mis-stating the fixed-point set as "tuples fixed by some rotation" instead of "tuples fixed by the generator \(\sigma\) of \(C_p\)" — for a cyclic group of prime order every non-identity element already generates the whole group, so this distinction only matters conceptually, but students often garble the orbit-stabiliser step by picking the wrong group element to test.

Discussion

Cauchy first proved this result for permutation groups in 1845, well before the abstract group axioms had been fully crystallised; the general statement for arbitrary finite groups came later once Cayley's theorem (every group embeds in a symmetric group) made the reduction available. The proof reproduced above, however, is not Cauchy's original argument — it is James H. McKay's 1959 one-page proof, which replaced an inductive argument through the class equation with a self-contained counting argument and is now the standard textbook proof precisely because it needs no case split between abelian and non-abelian groups.

The classical alternative proof proceeds by strong induction on \(|G|\): if \(G\) is abelian, pick any non-identity \(x\), and either \(p \mid \mathrm{ord}(x)\) (in which case some power of \(x\) already has order \(p\)) or one passes to the quotient \(G/\langle x \rangle\), which is smaller and still has \(p\) dividing its order; if \(G\) is non-abelian, the class equation \(|G| = |Z(G)| + \sum [G:C_G(g_i)]\) is used, splitting into the case \(p \mid |Z(G)|\) (apply the abelian case to the centre) versus \(p \nmid |Z(G)|\) (some conjugacy class term is coprime to \(p\), forcing \(p\) to divide a smaller centraliser, to which induction applies). Both proofs are complete and correct; McKay's is preferred for exposition because it is proof by direct construction of a large fixed-point set rather than by induction with a case split.

The counting technique in Steps 4–8 is a special, minimal instance of Burnside's lemma / the Cauchy–Frobenius orbit-counting formula, specialised to a cyclic group of prime order acting on a set, and reduced modulo \(p\) rather than averaged over the group order. This "orbit sizes divide the acting group's order, and constant tuples are the size-1 orbits" pattern reappears throughout combinatorics (e.g. in Fermat's little theorem itself, which is the \(G = \mathbb{Z}/p\mathbb{Z}\)-free special case of this very argument applied to necklace-counting) and in the proof of Sylow's first theorem, where the same rotation trick is run on \(p\)-subsets rather than \(p\)-tuples.

Common misconception: students often think Cauchy's theorem requires \(G\) to be abelian, presumably because the easiest textbook illustrations (e.g. \(\mathbb{Z}/n\mathbb{Z}\)) are abelian. The theorem is fully general; the McKay proof above never uses commutativity anywhere — every step manipulates tuples and rotations, which are defined identically whether or not \(G\) is abelian.

Worked examples

Ex 1

G = S_4,\quad |G| = 24 = 2^3 \cdot 3

Since \(3 \mid 24\), Cauchy's theorem guarantees an element of order \(3\) in \(S_4\). A

Ex 1.1

\sigma = (1\,2\,3) \in S_4

Exhibiting the guaranteed element directly: a 3-cycle has order exactly \(3\) since \(\sigma^3 = \mathrm{id}\) and \(\sigma, \sigma^2 \ne \mathrm{id}\) (a \(3\)-cycle's order equals its cycle length, a standard fact about disjoint cycle structure). This confirms the existence claim concretely rather than merely asserting it abstractly. A

(1\,2\,3) \in S_4 \text{ has order } 3

Reading. The theorem's existence claim is witnessed explicitly; note the theorem itself never needed to construct \(\sigma\) — it only guaranteed some element of order \(3\) exists, via the counting argument.

Ex 2

G = (\mathbb{Z}/15\mathbb{Z})^{\times},\quad |G| = \varphi(15) = 8

Setting up a genuinely non-obvious application: the group of units mod \(15\) has order \(\varphi(15) = \varphi(3)\varphi(5) = 2 \cdot 4 = 8\). We ask whether \(G\) has an element of order \(2\). A

Ex 2.1

2 \mid 8 = |G|

Since \(2\) is prime and divides \(|G| = 8\), Cauchy's theorem guarantees an element of order exactly \(2\) in \(G\) — without this theorem we would only know (from Lagrange) that element orders divide \(8\), not that order \(2\) is actually attained. B

Ex 2.2

14 \equiv -1 \pmod{15},\qquad 14^2 = 196 \equiv 1 \pmod{15}

Direct verification: \(196 = 13\cdot 15 + 1\), so \(14^2 \equiv 1\), and \(14 \not\equiv 1 \pmod{15}\), so \(\mathrm{ord}(14) = 2\) in \(G\), confirming the guarantee. Note \(G \cong \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/4\mathbb{Z}\) has three elements of order \(2\) here (namely \(4, 11, 14\)), more than Cauchy's minimum guarantee of one. A

14^2 \equiv 1 \pmod{15},\ \ 14 \not\equiv 1 \Rightarrow \mathrm{ord}(14)=2

Reading. Cauchy's theorem predicted, purely from \(2 \mid 8\), that such an element had to exist before any element was exhibited; the arithmetic check simply confirms the guaranteed existence.

Problems

Let \(|G| = 35\). Using Cauchy's theorem, show \(G\) has elements of order \(5\) and of order \(7\).
Solution
\(35 = 5 \cdot 7\) with \(5, 7\) both prime, and both divide \(|G| = 35\). By Cauchy's theorem applied with \(p = 5\), \(G\) has an element \(x\) with \(\mathrm{ord}(x) = 5\); applied with \(p = 7\), \(G\) has an element \(y\) with \(\mathrm{ord}(y) = 7\). (In fact one can go further with Sylow theory to show \(G\) is cyclic of order \(35\), but that is beyond what Cauchy's theorem alone gives.)
Explain precisely why Cauchy's theorem does not guarantee an element of order \(4\) in a group of order \(12\), even though \(4 \mid 12\).
Solution
Cauchy's theorem requires the divisor to be prime; \(4 = 2^2\) is not prime, so the hypothesis is not met and the theorem simply does not apply — it is silent, not violated. Indeed \(A_4\) has order \(12\) and no element of order \(4\) (its elements have orders \(1, 2, 3\) only), showing the extension to composite divisors is genuinely false, not just unproved.
Let \(G\) be a finite group with \(|G| = 2m\) where \(m\) is odd, \(m \gt 1\). Show \(G\) has an element of order \(2\). Then, using the left-regular permutation representation of \(G\) (Cayley's theorem), show \(G\) in fact has a normal subgroup of order \(m\) — so this particular composite divisor is always realised, unlike the general case (contrast with \(A_4\), order \(12\), which has no subgroup of order \(6\), a divisor that is not of the form "index \(2\)").
Solution
Element of order 2. Since \(2\) is prime and \(2 \mid 2m = |G|\), Cauchy's theorem directly supplies \(x \in G\) with \(\mathrm{ord}(x) = 2\).
Subgroup of order \(m\). Let \(G\) act on itself by left multiplication; this embeds \(G\) into \(\mathrm{Sym}(G) \cong S_{2m}\) (Cayley's theorem), and under this embedding \(x\) acts as a fixed-point-free permutation of the \(2m\) elements of \(G\) (fixed-point-free because \(gx = g \Rightarrow x = e\), false). A fixed-point-free permutation of order \(2\) decomposes into disjoint \(2\)-cycles covering all \(2m\) points, i.e. into exactly \(m\) transpositions. Since \(m\) is odd, this permutation is odd (a product of an odd number of transpositions has sign \(-1\)). Composing the embedding \(G \hookrightarrow S_{2m}\) with the sign homomorphism \(\mathrm{sgn}: S_{2m} \to \{\pm 1\}\) gives a group homomorphism \(\varphi : G \to \{\pm 1\}\) with \(\varphi(x) = -1\), so \(\varphi\) is surjective (non-trivial image inside a group of order \(2\)). By the First Isomorphism Theorem, \(\ker\varphi \trianglelefteq G\) and \(G/\ker\varphi \cong \{\pm1\}\), so \([G:\ker\varphi] = 2\), giving \(|\ker\varphi| = m\). Thus \(\ker\varphi\) is the required normal subgroup of order \(m\).
Let \(G\) be an abelian group of order \(45\). Use Cauchy's theorem to show \(G\) contains a subgroup isomorphic to \(\mathbb{Z}/15\mathbb{Z}\).
Solution
\(45 = 3^2 \cdot 5\). Since \(3 \mid 45\), Cauchy's theorem gives \(x \in G\) with \(\mathrm{ord}(x) = 3\); since \(5 \mid 45\), it gives \(y \in G\) with \(\mathrm{ord}(y) = 5\). Because \(G\) is abelian, \(xy = yx\), and a standard lemma (order of a product of commuting elements of coprime order) gives \(\mathrm{ord}(xy) = \mathrm{ord}(x)\cdot\mathrm{ord}(y) = 15\), since \(\gcd(3,5)=1\). [Proof of the lemma: if \((xy)^k = e\) then \(x^k = y^{-k}\) lies in \(\langle x \rangle \cap \langle y \rangle\), a subgroup whose order divides both \(3\) and \(5\) hence is \(1\), so \(x^k = y^k = e\), forcing \(3 \mid k\) and \(5\mid k\), so \(15 \mid k\); and \((xy)^{15}=x^{15}y^{15}=e\) shows the order is exactly \(15\).] So \(\langle xy \rangle \le G\) is cyclic of order \(15\).
A finite group \(G\) has order \(2^k\) for some \(k \ge 1\) (a "2-group"). Use Cauchy's theorem to prove that every non-identity element of \(G\) has order a power of \(2\), and deduce that if \(|G| \gt 1\) then \(G\) has an element of order exactly \(2\).
Solution
Let \(x \in G\), \(x \ne e\), with \(\mathrm{ord}(x) = d\). By Lagrange's theorem \(d \mid |G| = 2^k\), so \(d = 2^j\) for some \(0 \le j \le k\); since \(x \ne e\), \(d \ne 1\), so \(j \ge 1\) and \(d\) is indeed a power of \(2\) (this direction only needed Lagrange, not Cauchy). For existence of an element of order exactly \(2\): since \(|G| = 2^k \gt 1\), the prime \(2\) divides \(|G|\), so Cauchy's theorem directly supplies an element of order \(2\) — no need to first find an element of order \(2^j\) and take a power, though that route also works: take any non-identity \(x\) of order \(2^j\) and consider \(x^{2^{j-1}}\), which has order exactly \(2\) (a power of an order-\(m\) element has order \(m/\gcd(m,\text{power})\), a standard order-of-a-power lemma).