Let be a finite group and let be a prime dividing . Let denote the set of all -tuples of elements of whose product is 1. That is, . Now define a relation on as follows: if and only if is a cyclic permutation of .
- Prove that has elements, hence has order divisible by .
- Prove that a cyclic permutation of an element of is again in .
- Prove that is an equivalence relation.
- Prove that an equivalence class contains a single element if and only if it is of the form for some with .
- Prove that every equivalence class has order 1 or p. Deduce that , where is the number of classes of size 1 and is the number of classes of size .
- Noting that is a class of size 1, deduce that there exists a nonidentity element such that .
- We prove this equality by attempting to choose an arbitrary element of . Note that the first elements of an arbitrary tuple in may be chosen arbitrarily – with choices for each; a total of distinct choices. This having been done, the last entry is determined uniquely, namely . This exhausts all possible ways of choosing an element of , so that .
- Suppose , and let be a cyclic permutation. Then , so that . Thus the cyclic permutation is in .
- Every -tuple is trivially a cyclic permutation of itself, so that is reflexive.
- If is a cyclic permutation of , say by slots, then may be recovered by cyclically permuting times.
- If is the -th cyclic permutation of and the -th cyclic permutation of , then is the -th cyclic permutation of .
Hence is an equivalence relation.
- Let be a equivalence class containing a single element, and let . Now the -th cyclic permutation of is again , so that for all such . Thus .
- Suppose has exactly distinct cyclic permutations; note that . Now for each , we have , where indices are taken mod . More generally, for each and , with indices taken modulo . Suppose does not divide ; since is prime, then, . We saw previously that ranges over all residue classes of , so that for some . Otherwise, divides , so that (and ) or . Hence every is in a -equivalence class of size 1 or p. Counting elements of , then, we have where is the number of size 1 equivalence classes and the number of size equivalence classes.
- Since divides and , we have where is the number of size 1 equivalence classes. Hence , and there exists at least one size one equivalence class which is not trivial – i.e., has the form for some nonidentity . Thus there exists an element such that .