A partial sketch of proof (of the sufficiency):
You can first prove that and always generate by showing that they generate the transpositions , and then any transposition (note that if I'm not mistaking).
If and are relatively prime, it suffices to show that is in the group generated by and . The idea is very similar to the proof of the first case. Let . First show that you can get the transpositions , and then find by composing the previous ones in a neat way (very much like the first case).