- Show that the transpositions for generate .
- Show that any transposition can be obtained from and .
We also need the following key lemma the proof of which is routine.
Lemma. for any and .
(1) is easily proven by the observation that any permutation of can be obtained by swapping two elements at a time. (2) is a bit more interesting.
We first use the lemma to observe that any transposition of the form can be obtained from upon repeated conjugation by . Now, since , WLOG let . Using the lemma, conjugating by gives , conjugating by gives , etc. In this way we can eventually get . So we are done by (1).
This argument shows that can in fact be generated by and for any .
Now let’s consider an arbitrary transposition and an -cycle in . By relabeling , we can assume that and for . Note that where , so WLOG . Then for each . In particular, taking gives . Then . Repeating this procedure produces for . Now is a complete set of residues mod if and only if , i.e., . So we’ve shown that
Theorem. Let be a transposition and be an -cycle in . Then and generate if and only if .
In particular, and generate if and only if .
Corollary. is generated by any transposition and any -cycle for prime.