# Proof by induction involving symmetric groups

I am aware that i have posted this question before, but the comments i received did not really help silly old me. So i would appreciate it if someone can walk me through some parts of the problem. I have revised my attempt from the previous post, accounting for the comments i have received as i understood them.

Let $$n>1$$ be a natural number. the m-cycle $$\sigma=(a_1,a_2,a_3,\dots,a_m)$$ denotes a permutation in $$S_n$$ where $$\sigma(a_1)=a_2,\sigma(a_2)=a_3,\dots, \text{ and }\sigma(a_m)=a_1$$.

Prove by induction on $$k \geq 1$$ that if $$k+i\equiv j (mod\text{ m})$$, then $$\sigma^k(a_i)=a_j$$ whenever $$1\leq i \leq m$$ and $$1\leq j \leq m$$.

Pained Attempt :

Let $$n>1$$ be a natural number. the m-cycle $$\sigma=(a_1,a_2,a_3,\dots,a_m)$$ denotes a permutation in $$S_n$$ where $$\sigma(a_1)=a_2,\sigma(a_2)=a_3,\dots, \text{ and }\sigma(a_m)=a_1$$.

[Base Step]

For the base case,$$k=1$$, assume that $$1+i\equiv j (mod\text{ m})$$ and prove that $$\sigma^1(a_i)=a_j$$ whenever $$1\leq i \leq m$$ and $$1\leq j \leq m$$.

Since $$1+i\equiv j (mod\text{ m})$$ then $$j \equiv 1+i (mod\text{ m})$$ and $$m | j-(1+i)$$ hence $$j = mh+i+1$$ for some $$h \in \Bbb{Z}$$.

[case:$$1 \leq i \lt m$$]

Since $$j=mh+i+1$$ then $$a_j=a_{mh+i+1}$$. By assumption $$\sigma(a_{mh+i})=a_{mh+i+1}=a_j$$.

I am not sure how to proceed further here..

I thought: With $$1 \leq i \lt m$$ and mh+i+1 being constrained to lie between 1 and m given the definition of the m-cycle, this implies that h must be 0 (?).Therefore $$\sigma(a_{m(0)+i})=a_{m(0)+i+1}=a_j$$ and $$\sigma(a_{i})=a_{i+1}=a_j$$ as required (?)

...this feels iffy.

[case: $$i=m$$]

Since $$j=mh+i+1$$ then $$a_j=a_{mh+m+1}$$ and $$a_j=a_{m(h+1)+1}$$ . By assumption $$\sigma(a_{m(h+1)})=a_{m(h+1)+1}=a_j$$.

I am not sure how to proceed further either..

Any help would be much appreciated.

• When reposting a question, you should link to the old question. It's also good to be as specific as possible about what you didn't understand about the given responses. – Theo Bendit May 2 at 7:33

You are getting hung up on completely irrelevant details. Once you know $$k$$ and $$i$$, you know $$j$$. There's no need to delve into modular arithmetic and introduce new variables. Here's a complete proof of the base step:

Base case:

Let $$k=1$$ and let $$1\leq i,j\leq m$$ be such that $$k+i\equiv j\pmod{m}$$. We distinguish two cases:

1. If $$1\leq i then $$1 and so $$j=k+i=1+i$$. Then $$\sigma^1(a_i)=\sigma(a_i)=a_{i+1}=a_j$$.
2. If $$i=m$$ then $$k+i=m+1$$ and so $$j=1$$. Then $$\sigma^1(a_i)=\sigma(a_m)=a_1=a_j$$.

Can you now prove the induction step?

• You are given as the definition of $\sigma$ that $\sigma(a_m)(=\sigma^1(a_m))=a_1$. That step is where the modulo comes in. – Robert Shore May 2 at 8:15
• @HalfAFoot Since $k=1$ and $i=m$, it is immediate from the definition that $$1+m\equiv j\pmod{m}.$$ Everything you wrote before that is completely irrelevant. Further, the implication $$m\mid(j-1)\quad\implies\quad m\leq(j-1),$$ is false. Instead simply note that $$1+m\equiv 1\pmod{m}\qquad\text{ so }\qquad j\equiv1\pmod{m}.$$ Because $1\leq j\leq m$ it follows that $j=1$. Do not focus on the modular arithmetic, it is just a formality here. – Servaes May 2 at 10:20
• What do you mean by 'artificially choosing'? For any value of $x$ the congruence $$j\equiv x\pmod{m},$$ has a unique solution $j$ with $1\leq j\leq m$. For $x=1$ this is clearly $j=1$. – Servaes May 2 at 10:44
• I do not understand your question. It should be more than obvious that $1+m\equiv1\pmod{m}$ by definition. – Servaes May 2 at 10:51
• @Servaes, you are ofcourse right..! Thank you very much for walking me through this :) ...i did not realise your point about there being a unique solution j with 1<=j<=m..after flipping through my book the closest result i have found is : For each integer a there is exactly one integer r in the list 0,...,m-1 s.t. a is congruent to r (modulo m) or more precisely : 0<=r<m...Thanks again – HalfAFoot May 2 at 11:02