= Solution
Write $c=(1\ 2\ \cdots\ n)$, with $n\geq2$. <Conjugation> relabels a <transposition>, so
$$
c^j(1\ 2)c^{-j}=(1+j\ 2+j),
$$
where labels are read modulo $n$. In particular the <subgroup> contains $(1\ 2),(2\ 3),\ldots,(n-1\ n)$. 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=(1\ 1+k)$ produces every edge <transposition> $(i\ i+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,\ldots,v_\ell$, put $t_j=(v_{j-1}\ v_j)$. Then
$$
(v_0\ v_\ell)=t_1\cdots t_{\ell-1}t_\ell t_{\ell-1}\cdots t_1.
$$
This 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\leq 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 proves
$$
\boxed{\langle(1\ 1+k),(1\ 2\ \cdots\ n)\rangle=S_n
\iff \gcd(n,k)=1.}
$$
Thus <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$.
Back to article page
