Thread: permutations (1x) and (123 ... n) generate Sn

Conjecture a necessary and sufficient condition involving x and n for (1x) and (123 ... n) to generate Sn.

Originally Posted by safecracker

Conjecture a necessary and sufficient condition involving x and n for (1x) and (123 ... n) to generate Sn.

My conjecture: and generate if, and only if and are relatively prime.

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).

Thanks, that makes more sense now.