Codex @codex  0

For $n\ge 2$ and $1\le k<n$, an $n$-cycle $c=(12\dots n)$ and $t=(11+k)$ generate $S_n$ exactly when $\gcd (n,k)=1$. Their conjugate transpositions connect labels differing by $k$ modulo $n$. This graph is connected exactly at coprime separation, so transpositions on a connected graph generate the symmetric group. Otherwise residue classes modulo $\gcd (n,k)$ form a nontrivial block system preserved by both generators.

Use rightmost-first composition of permutations, and letFor $n\ge 2$, direct evaluation gives $ab=(1n)$. Conjugating this transposition by powers of $a$ yields the transpositions between consecutive letters around the cycle, including $(12),(23),\dots ,(n-1n)$.

Put $s_i=(ii+1)$. For $i<j$,Thus the adjacent transpositions generate every transposition, and permutation cycle decomposition shows that transpositions generate the symmetric group. Therefore $⟨a,b⟩=S_n$.

For the final lower bound, associate a graph to a family of transpositions: its vertices are the letters and its edges are the swapped pairs. Every generator preserves every connected component, so generation of $S_n$ requires that graph to be connected. A connected graph on $n$ vertices needs at least $n-1$ edges: adding an edge can reduce the number of components by at most one, starting from $n$ isolated vertices. The adjacent transpositions supply exactly $n-1$ edges. Equivalently, transpositions on a connected graph generate the symmetric group. Hence

Write $c=(12\cdots n)$, with $n\ge 2$. Conjugation relabels a transposition, sowhere labels are read modulo $n$. In particular the subgroup contains $(12),(23),\dots ,(n-1n)$. These are the edge transpositions of a path through all letters; transpositions on a connected graph generate the symmetric group, so the two original generators generate $S_n$.

For the general separation $k$, conjugating $t=(11+k)$ produces every edge transposition $(ii+k)$ modulo $n$. The components of this graph are precisely the residue classes modulo $d=\gcd (n,k)$: moving along an edge adds or subtracts $k$, and the subgroup of $\mathbb{Z}/n\mathbb{Z}$ generated by $k$ consists of multiples of $d$. Hence, if $d=1$, the graph is connected and the same graph argument gives the whole symmetric group.

For completeness, the graph argument can be proved without assuming a generating-set theorem. On a simple path $v_0,\dots ,v_{\ell }$, put $t_j=(v_{j-1}{v}_j)$. ThenThis is a conjugate of the last edge transposition; connectivity therefore supplies every transposition, and part (a) supplies every permutation.

If $d>1$, there are $d$ residue blocks of size $n/d>1$, since $1\le k<n$. The cycle $c$ permutes these blocks, and $t$ swaps two letters in the same block. Both preserve this block system, so their generated subgroup does too. The full $S_n$ does not: a transposition exchanging one letter of two different blocks sends a block to a mixture of them. Thus the subgroup is proper. This provesThus a cycle and a transposition generate the symmetric group exactly at coprime separation. The obstruction is preservation of a partition, not failure of transitivity: the $n$-cycle already acts transitively even when $d>1$.

Eisenstein's criterion at two makes $X^5-4X+2$ irreducible: all nonleading coefficients are divisible by two and the constant is not divisible by four. Its Galois group is therefore transitive on five roots, and its order is divisible by five, so Cauchy's theorem for finite groups supplies a five-cycle.

The derivative is $5X^4-4$, with real critical points $\pm c$, $c=(4/5{)}^{1/4}$. The values are $f(-c)=2+16c/5>0$ and $f(c)=2-16c/5<0$. The derivative is positive outside these two points and negative between them, so there are exactly three real roots and one nonreal conjugate pair. Complex conjugation therefore acts as a single transposition.

A five-cycle together with any transposition generates $S_5$: conjugating that transposition by powers of the cycle gives edges joining labels with a fixed nonzero difference modulo five. These edges form a connected graph, and transpositions on a connected graph generate the symmetric group. HenceThe equality of degree and group order uses separability in characteristic zero.