3
$\begingroup$

I was working on the following problem:

Let $\sigma$ be the m-cycle $(1 2...m)$. Show that $\sigma^{i}$ is also an m-cycle iff $\gcd(i,m)=1$

A solution to this problem is given here.

But the solution I came up with doesn't seem as rigorous as the one given, so I wasn't sure if it is correct.

My attempted solution:

Suppose that $\operatorname{gcd}(i,m)=n$ where $1<n < m$.

Then we have:

$\sigma^{i}(a_{x_{1}})=a_{x_{2}}, \sigma^{i}(a_{x_{2}})=a_{x_{3}},...,\sigma^{i}(a_{x_{n}})=a_{x_{1}}$ where each of $a_{x_{j}}$ is an arbitrary element of $[1,2,3,4,....m]$

And since $n<m$, we have formed an n-cycle.

Thus $\operatorname{gcd}(i,m)=1$.

Now if $\operatorname{gcd}(i,m)=1$, then we have,

$\sigma^{i}(a_{x_{1}})=a_{x_{2}}, \sigma^{i}(a_{x_{2}})=a_{x_{3}},...,\sigma^{i}(a_{x_{m}})=a_{x_{1}}$ which forms an m-cycle.

Is this attempt correct?

Also if possible, can you give a shorter solution than the one given in the link above.

$\endgroup$
  • $\begingroup$ added "gcd" throughout your post, please double check that I haven't changed what you intended to write $\endgroup$ – angryavian Jan 3 '16 at 19:42
1
$\begingroup$

Personally I believe that you should add an explanation on why when $\text{gcd}(i,m)=n$ then you have $\sigma^i(a_{x_n})=a_{x_1}$. A similar problem can found in the case $\text{gcd}(i,m)=1$, you should add the details.

Then you should probably explain why this implies that $\sigma^i$ is not an $m$-cycle, of course one could say that from that it follows that $\sigma^i$ factors through an $n$-cycle, with $n < m$, so it cannot be an $m$-cycle.

It could be possible to provide a shorter proof but it would probably hide much of the lemmas of the proof in the link you gave.... so it could sound a little bit like cheating.

$\endgroup$
0
$\begingroup$

The ideas in your attempt are good, but not well explained. The second part is insufficiently motivated.

You have $$ \sigma^1(1)=2,\quad \sigma^2(1)=3,\quad \dots $$ (assuming $m\ge3$, of course). In general, $$ \sigma^i(k)=k+(i\bmod m) $$ as you can prove by an easy induction, where $i\bmod m$ denotes the remainder of the division of $i$ by $m$, with $0\le i\bmod m<m$.

Let $d=\gcd(i,m)$ and start from $1$. The first time you get back to $1$, successively applying $\sigma^i$, is after $m/d$ steps.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.