## Alternate proof of Cauchy’s Theorem

Let $G$ be a finite group and let $p$ be a prime dividing $|G|$. Let $\mathcal{S}$ denote the set of all $p$-tuples of elements of $G$ whose product is 1. That is, $\mathcal{S} = \{ (x_1, x_2, \ldots, x_p) \ |\ x_i \in G\ \mathrm{and}\ x_1x_2 \ldots x_p = 1 \}$. Now define a relation $\sim$ on $\mathcal{S}$ as follows: $\alpha \sim \beta$ if and only if $\beta$ is a cyclic permutation of $\alpha$.

1. Prove that $\mathcal{S}$ has $|G|^{p-1}$ elements, hence has order divisible by $p$.
2. Prove that a cyclic permutation of an element of $\mathcal{S}$ is again in $\mathcal{S}$.
3. Prove that $\sim$ is an equivalence relation.
4. Prove that an equivalence class contains a single element if and only if it is of the form $(x,x,\ldots,x)$ for some $x$ with $x^p = 1$.
5. Prove that every equivalence class has order 1 or p. Deduce that $|G|^{p-1} = k+pd$, where $k$ is the number of classes of size 1 and $d$ is the number of classes of size $p$.
6. Noting that $\{(1,1,\ldots,1)\}$ is a class of size 1, deduce that there exists a nonidentity element $x \in G$ such that $x^p = 1$.

1. We prove this equality by attempting to choose an arbitrary element of $\mathcal{S}$. Note that the first $p-1$ elements $x_1,x_2, \ldots, x_{p-1}$ of an arbitrary tuple in $\mathcal{S}$ may be chosen arbitrarily – with $|G|$ choices for each; a total of $|G|^{p-1}$ distinct choices. This having been done, the last entry is determined uniquely, namely $(x_1 x_2 \ldots x_{p-1})^{-1}$. This exhausts all possible ways of choosing an element of $\mathcal{S}$, so that $|\mathcal{S}| = |G|^{p-1}$.
2. Suppose $(x_1,x_2,\ldots,x_p) \in \mathcal{S}$, and let $(x_k,x_{k+1},\ldots,x_p,x_1,\ldots,x_{k-1})$ be a cyclic permutation. Then $(x_1x_2\ldots x_{k-1})(x_k x_{k+1}\ldots x_p) = 1$, so that $(x_k x_{k+1}\ldots x_p)(x_1x_2\ldots x_{k-1}) = 1$. Thus the cyclic permutation is in $\mathcal{S}$.
1. Every $p$-tuple is trivially a cyclic permutation of itself, so that $\sim$ is reflexive.
2. If $\sigma$ is a cyclic permutation of $\tau$, say by $k$ slots, then $\tau$ may be recovered by cyclically permuting $\sigma$ $p-k$ times.
3. If $\sigma$ is the $k$-th cyclic permutation of $\tau$ and $\theta$ the $\ell$-th cyclic permutation of $\sigma$, then $\theta$ is the $k+\ell$-th cyclic permutation of $\tau$.

Hence $\sim$ is an equivalence relation.

3. $(\Rightarrow)$ Let $\{ \sigma = (x_1,x_2,\ldots,x_p) \}$ be a $\sim$ equivalence class containing a single element, and let $1 \leq k \leq p$. Now the $k$-th cyclic permutation of $\sigma$ is again $\sigma$, so that $x_k = x_1$ for all such $k$. Thus $\sigma = (x,x,\ldots,x)$.

$(\Leftarrow)$ Trivial.

4. Suppose $\sigma \in \mathcal{S}$ has exactly $k$ distinct cyclic permutations; note that $k \leq p$. Now for each $1 \leq i \leq p$, we have $x_i = x_{k+i}$, where indices are taken mod $p$. More generally, $x_i = x_{ak+i}$ for each $i$ and $a \in \mathbb{Z}$, with indices taken modulo $p$. Suppose $k$ does not divide $p$; since $p$ is prime, then, $\mathsf{gcd}(k,p) = 1$. We saw previously that $ak+1$ ranges over all residue classes of $\mathbb{Z}/(p)$, so that $\sigma = (x,x,\ldots,x)$ for some $x \in G$. Otherwise, $k$ divides $p$, so that $k = 1$ (and $\sigma = (x,x,\ldots,x)$) or $k = p$. Hence every $\sigma \in \mathcal{S}$ is in a $\sim$-equivalence class of size 1 or p. Counting elements of $\mathcal{S}$, then, we have $|G|^{p-1} = k+pd$ where $k$ is the number of size 1 equivalence classes and $d$ the number of size $p$ equivalence classes.
5. Since $p$ divides $|G|$ and $pd$, we have $p|k$ where $k$ is the number of size 1 equivalence classes. Hence $k > 1$, and there exists at least one size one equivalence class which is not trivial – i.e., has the form $\{ (x,x,\ldots,x) \}$ for some nonidentity $x \in G$. Thus there exists an element $x \in G$ such that $x^p = 1$.
In problem 1, the last entry $x_p$ should be $(x_1 x_2 \cdots x_{p-1})^{-1}$.