Prove that every element of the symmetric group $S_{n}$ is a product of transpositions. [You may assume without proof that every permutation is the product of disjoint cycles.]

(a) Define the sign of a permutation in $S_{n}$, and prove that it is well defined. Define the alternating group $A_{n}$.

(b) Show that $S_{n}$ is generated by the set $\left\{\left(\begin{array}{lll}1 & 2\end{array}\right),\left(\begin{array}{llll}1 & 2 & 3 & \ldots\end{array}\right)\right\}$.

Given $1 \leqslant k<n$, prove that the set $\left\{\left(\begin{array}{ll}1 & \left.1+k),\left(\begin{array}{lll}1 & 2 & 3\end{array} \ldots n\right)\right\} \text { generates } S_{n} \text { if and only }\end{array}\right.\right.$ if $k$ and $n$ are coprime.