In an earlier post, I asked for some intuition on Cauchy's Theorem for Groups (for every prime divisor of the order of a finite group, there exists an elements who's order is that prime). I got great answers and was made aware of this incredible proof by McKay. Personally I think its a gorgeous proof, and love the insight he provides in the opening paragraph. However, I'm having difficulty with a single claim he makes.
"Otherwise, if two components of a p-tuple are distinct, there are p members in the equivalence class."
To summarize his claim. suppose $p$ is a prime that divides the order of some group $G$ and consider the string
$$x_1x_2\dots x_p = e$$
then if there exists $i,j$ such that $x_i = x_j, i\ne j$ then for any cyclic permutation of these elements, the strings of elements are not identical.
I can't quite see how this conclusion can be made on the distinctness of a single pair of components. Wouldn't this claim imply that if $g_1g_2\dots g_p = e, g_i\ne e$ than all the $g_i$'s are distinct?
Thanks for the help as always!
Best Answer
Below is a presentation that I devised to clarify McKay's proof (from an old sci.math post).
Lemma $\ $ If $g$ is an element of a group and $p$ is prime then $g^p = 1\:\Rightarrow\:$ $g$ has order $p$ or $1$.
Proof $\ $ If $g$ has order $n$ then $g^n = g^p = 1 \Rightarrow\ g^{(n,p)} = 1.$ But $(n,p) = p$ or $1$ by $p$ prime.
Theorem $\ $ Suppose that $p$ is prime, $G$ is a finite group of order $n,$ and $R =$ #$p$'th roots of $1$ in $G,$ i.e. $\: R = \#\{ g \in G :\ g^p = 1 \}.\:$ Then
$$ R \equiv n^{p-1}\ ({\rm mod}\ p),\ \ {\rm and}\ \ R > 1 \iff p\mid n$$
Proof $\ $ Let $S$ be the set of all $p$-tuples of elements from $G$ whose product is $1,$ i.e.
$$ S = \{ (g_1,g_2,\ldots,g_p) :\ g_1 g_2\cdots g_p = 1,\ g_i \in G \}$$
Let $F$ be the cyclic rotation on $p$-tuples
$$ F(\color{#C00}{g_1},g_2,\ldots,g_p) = (g_2,g_3,\ldots,g_p,\color{#C00}{g_1}) $$
Clearly $F^p = 1,$ so $F$ is a permutation on $S.$ Recall that a permutation $F$ decomposes into disjoint cycles (orbits) $\:\langle F\rangle s = \{F^k s :\, k \in \Bbb Z\},$ the classes of the equivalence relation $s \sim t \!\iff\! s = F^k t,$ for some $k \in \Bbb Z.$ Thus the cycles of $F$ form a partition $S = \langle F\rangle s_1 \cup \cdots \cup \langle F\rangle s_m.$
Consider the permutation $F$ restricted to some cycle $C.$ Notice the order of $F$ on $C$ is the cycle length $n$ of $C.$ But since $F^p = 1,$ the lemma implies that $n = p$ or $1.$ So $S$ decomposes into disjoint cycles of length $p$ or $1,$ yielding one count for $|S|$. For another, notice $S$ has $n^{p-1}$ elements since, after freely choosing the first $p-1$ elements of a $p$-tuple in $S,$ the last element must be the inverse of the product of the others. Comparing both counts
$$ |S| = n^{p-1}\! =\, Q\,p + R,\ \ \ Q = \#p{\rm\!-\!cycles,}\ \ R = \#1{\rm\!-\!cycles} $$
A $\:1$-cycle has $Fs = s,$ so $s$ has all entries identical, say $g,$ so $g^p = 1,$ i.e. $g$ is a $p$'th root of $1$ in $G$ iff $g$ is a $1$-cycle of $R.$ Hence mod $p: n^{p-1} = R,$ the number of $p$'th roots of $1$ in $G.$ If $p\mid n$ then $p\mid R.$ But $R > 0$ since always $1^p = 1,$ hence $R \ge p > 1.$ Conversely, if $R > 1$ then $G$ has $g \ne 1$ with $g^p = 1,$ so the lemma implies $g$ has order $p.$ But also $g^n = 1,$ so $p\mid n.\ \ $ QED
Corollary 1 $\ $ (Cauchy's Theorem) $\ $ If a group $G$ has order $n$ divisible by a prime $p$ then $G$ has a subgroup of order $p.$
Proof $\ \ p\mid n\:$ so the theorem implies $R > 1,$ i.e. $G$ has a $g \ne 1$ with $g^p = 1.$ The lemma implies that $g$ has order $p,$ so $g$ generates a cyclic subgroup $\langle g\rangle$ of order $p.$
Corollary 2 $\ $ (F$\ell$T: Fermat's $\ell$ittle Theorem) $\ $ If $p$ is prime and $p\nmid n$ then $n^{p-1} \equiv 1 \pmod p.$
Proof $\ $ Apply the theorem to any (e.g. cyclic) group of order $n.$
Corollary 3 $\ \ $ Theorem $\Rightarrow$ Lemma
Proof $\ $ Suppose $g^p = 1,\ g \ne 1.$ Let $n$ be the order of $g.$ Apply the theorem to the cyclic group $\langle g\rangle$ generated by $g.$ Note $g^p = 1^p = 1\:\Rightarrow\: R > 1,$ so $p\mid n,$ therefore $n = p.$