# Thread: permutations (1x) and (123 ... n) generate Sn

1. ## permutations (1x) and (123 ... n) generate Sn

Conjecture a necessary and sufficient condition involving x and n for (1x) and (123 ... n) to generate Sn.

2. Originally Posted by safecracker
Conjecture a necessary and sufficient condition involving x and n for (1x) and (123 ... n) to generate Sn.
My conjecture: $(1\ x)$ and $(1\ \cdots\ n)$ generate $S_n$ if, and only if $x-1$ and $n$ are relatively prime.

A partial sketch of proof (of the sufficiency):

You can first prove that $(1\ 2)$ and $(1\ \cdots\ n)$ always generate $S_n$ by showing that they generate the transpositions $(k\ k+1)$, and then any transposition (note that $(1\ k)=(1\ 2)(2\ 3)\cdots(k-2\ k-1)(k-1\ k)(k-2\ k-1)\cdots(2\ 3)(1\ 2)$ if I'm not mistaking).

If $n$ and $x-1$ are relatively prime, it suffices to show that $(1\ 2)$ is in the group generated by $(1\ x)$ and $(1\ \cdots\ n)$. The idea is very similar to the proof of the first case. Let $p=x-1$. First show that you can get the transpositions $(k\ (k+p))$, and then find $(1\ 2)$ by composing the previous ones in a neat way (very much like the first case).

3. Thanks, that makes more sense now.