This is (part 1 of) Exercise 4.3.21 in D&F 3ed Abstract Algebra, which I have to prove:
Show that $\sigma \in S_n$ does not commute with any odd permutation if and only if the cycle type of $\sigma$ consists of distinct odd integers.
There also is a hint to go along with this:
Assume first that $\sigma \in S_n$ does not commute with any odd permutation. Observe that $\sigma$ commutes with each individual cycle in its cycle decomposition-- use this to show that all its cycles must be of odd length. If two cycles have the same odd length, $k$, find a product of $k$ transpositions which interchanges them and commutes with $\sigma$. Conversely, if the cycle type of $\sigma$ consists of distinct integers, prove that $\sigma$ commutes only with the group generated by the cycles in its cycle decomposition.
This took me more time to prove than I'd like to admit. I am uncertain about the correctness of the converse argument. Could you please verify the correctness of my proof, and possibly suggest ways to make it better?
Proof:
Proposition 10 (D&F pg. 125). Let $\sigma, \tau$ be elements of the symmetric group $S_n$ and suppose $\sigma$ has cycle decomposition $$ (a_1 \; a_2 \; ... \; a_{k_1})(b_1 \; b_2 \; \ldots \; b_{k_2})\ldots $$ Then $\tau\sigma\tau^{-1}$ has cycle decomposition $$ (\tau(a_1) \; \tau(a_2) \; ... \; \tau(a_{k_1}))(\tau(b_1) \; \tau(b_2) \; \ldots \; \tau(b_{k_2}))\ldots $$
$(\Longrightarrow)$: Assume $\sigma \in S_n$ does not commute with any odd permutation. $\sigma$ commutes with every cycle in it's cycle decomposition, so the cycle type of $\sigma$ is all odds. Assume that two cycles have the same odd length $n$. Let $\sigma'$ be their product $\sigma' = (a_1 \; \ldots \; a_n)(b_1 \; \ldots \; b_n)$. If $\tau = (a_1 \; b_1) \ldots (a_n \; b_n)$, then $\tau \sigma' \tau^{-1} = \sigma'$ because $$ \tau(a_1 \; \ldots \; a_n)\tau^{-1} = (b_1 \; \ldots \; b_n) \qquad \text{and} \qquad \tau(b_1 \; \ldots \; b_n)\tau^{-1} = (a_1 \; \ldots \; a_n) $$ Because $\tau$ is the product of $n$ transpositions and $n$ is odd, we have a contradiction. Thus, no two cycles have the same odd length.
$(\Longleftarrow)$: Conversely, assume that the cycle type of $\sigma$ consists of distinct odd integers. Let $\sigma$ commute with $\tau$: $\tau \sigma \tau^{-1} = \sigma$, and express $\sigma = \sigma_1\ldots\sigma_k$ as the product of cycles where $|\sigma_i| = p_i$. By Proposition 10 it follows that $\sigma = \tau\sigma\tau^{-1} = (\tau\sigma_1\tau^{-1}) \ldots (\tau\sigma_k\tau^{-1})$. Thus, $$ \tau\sigma_i\tau^{-1} = \sigma_j \implies p_i = p_j \implies i = j \implies \tau \sigma_i = \sigma_i \tau $$ (because the cycle type of $\sigma$ consists of distinct odd integers). In other words, $\tau$ commutes with every cycle $\sigma_i$ in $\sigma$. Fix a cycle $\tau_i$ of $\tau$. Because $\tau$ commutes with $\sigma_i$, we know $\tau_i$ commutes with $\sigma_i$. Thus $\tau_i \in C_{\text{Sym}(n)}(\{\sigma_i\})$. Because $\sigma_i$ commutes with it's powers, $\langle \sigma_i \rangle \subseteq C_{\text{Sym}(n)}(\{\sigma_i\})$, and because $|\sigma_i| = p_i$, it follows from Proposition 10 that there exist $p_i$ such $\tau_i$s; This implies $|C_{\text{Sym}(n)}(\{\sigma_i\})| = p_i$, or $C_{\text{Sym}(n)}(\{\sigma_i\}) = \langle \sigma_i \rangle$. This implies that $\tau_i \in \langle \sigma_i \rangle$, or that for all $1 \leq i \leq k$, we have $\tau_i = \sigma_i^{a_i}$. This implies $\sigma$ only commutes with the group generated by the cycles in its cycle decomposition. In other words, $\sigma$ only commutes with even permutations, not odd permutations. $\blacksquare$
Whew, that took a while to type up!