# Generating the symmetric group

It’s a fairly well-known fact that the symmetric group $S_n$ can be generated by the transposition $(1\ 2)$ and the $n$cycle $(1\ \cdots\ n)$. One way to prove it is as follows.

1. Show that the transpositions $(a\ b)$ for $a,b\in\{1,\dots,n\}$ generate $S_n$.
2. Show that any transposition $(a\ b)$ can be obtained from $(1\ 2)$ and $(1\ \cdots\ n)$.

We also need the following key lemma the proof of which is routine.

Lemma. $\rho (a\ b)\rho^{-1}=(\rho(a)\ \rho(b))$ for any $\rho\in S_n$ and $a,b\in\{1,\dots,n\}$.

(1) is easily proven by the observation that any permutation of $1,\dots,n$ 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 $(a\ a+1)$ can be obtained from $(1\ 2)$ upon repeated conjugation by $(1\ \cdots\ n)$. Now, since $(a\ b)=(b\ a)$, WLOG let $a. Using the lemma, conjugating $(a\ a+1)$ by $(a+1\ a+2)$ gives $(a\ a+2)$, conjugating $(a\ a+2)$ by $(a+2\ a+3)$ gives $(a\ a+3)$, etc. In this way we can eventually get $(a\ b)$. So we are done by (1).

This argument shows that $S_n$ can in fact be generated by $(a\ a+1)$ and $(1\ \cdots\ n)$ for any $a$.

Now let’s consider an arbitrary transposition $\tau$ and an $n$-cycle $\sigma$ in $S_n$. By relabeling $1,\dots,n$, we can assume that $\sigma=(1\ \cdots\ n)$ and $\tau=(a\ b)$ for $a. Note that $\sigma^{-a+1}\tau\sigma^{a-1}=(1\ c)$ where $c=b-a+1$, so WLOG $\tau=(1\ c)$. Then $\sigma^k\tau\sigma^{-k}=(1+k\ c+k)$ for each $k$. In particular, taking $k=c-1$ gives $\sigma^{c-1}\tau\sigma^{-c+1}=(c\ 2c-1)=:\rho$. Then $\rho\tau\rho^{-1}=(1\ 2c-1)$. Repeating this procedure produces $(1\ c+k(c-1))$ for $k=0,1,2,\dots$. Now $\{c+k(c-1):k=0,1,\dots,n-1\}$ is a complete set of residues mod $n$ if and only if $\gcd(c-1,n)=1$, i.e., $\gcd(b-a,n)=1$. So we’ve shown that

Theorem. Let $\tau=(a\ b)$ be a transposition and $\sigma=(c_1\ \cdots\ c_n)$ be an $n$-cycle in $S_n$. Then $\tau$ and $\sigma$ generate $S_n$ if and only if $\gcd(c_b-c_a,n)=1$.

In particular, $(a\ b)$ and $(1\ \cdots\ n)$ generate $S_n$ if and only if $\gcd(b-a,n)=1$.

Corollary. $S_p$ is generated by any transposition and any $p$-cycle for $p$ prime.