Proving Least Positive Residue Using m-Cycle Permutations

[Bashyboy]

Homework Statement

Prove that if $\sigma$ is the $m$-cycle $(a_1 ~ a_2 ... a_m)$, then for all $i \in \{1,...,m\}$, $\sigma^{i}(a_k) = a_{k+i}$, where $k+i$ is replaced by its least positive residue $\mod m$.

Homework Equations

The Attempt at a Solution

My question is embarrassingly simple. What is the least positive residue? Would it be that number $x \in \mathbb{Z}^+$ for which $x \equiv k+1 (\mod m)$?

 

[fresh_42]

Homework Statement

Prove that if $\sigma$ is the $m$-cycle $(a_1 ~ a_2 ... a_m)$, then for all $i \in \{1,...,m\}$, $\sigma^{i}(a_k) = a_{k+i}$, where $k+i$ is replaced by its least positive residue $\mod m$.

Homework Equations

The Attempt at a Solution

My question is embarrassingly simple. What is the least positive residue? Would it be that number $x \in \mathbb{Z}^+$ for which $x \equiv k+1 (\mod m)$?

It simply means the remainders in $\{1, \ldots , m\}$ which is necessary for the index $i+k$ to make sense.
E.g. You can write $16 = 2 \cdot 7 + 2$ or $16 = 1 \cdot 7 + 9$ or $16 = 4 \cdot 7 - 12$. All these numbers $2,9,-12$ are possible remainders of a division by $7$. However, we usually only consider the $2$ as the one we want to look at. And $2$ is the least positive one.

 

[Bashyboy]

Okay, I hate to revive this thread, but I haven't been able to look at the problem for some time. I am still having trouble with this least positive residue business. What happens if $k+1$ is a multiple of $m$? Wouldn't the remainder be zero, which is a not a positive number? Don't we need to prove that $k+1$ divided by $m$ has a least positive residue in $\{1,...,m\}$? I am not even sure I worded that last sentence correctly. I am trying to see the connection between the remainder you get from the division algorithm and the one the problem demands (i.e., the remainder in $\{1,...,m\}$).

 

[vela]

If $k+1$ is a multiple of $m$, then the least positive residue is $m$ for the reason you noted, i.e., 0 is not a positive number.

 

[Bashyboy]

Okay, I think I am starting to see now. Perhaps someone could help me with proving the theorem now. We will prove the theorem by induction. When $i=1$, we have the formula says $\sigma^1(a_k) = a_{k+1}$. Now, either $k+1 \in \{1,...,m\}$ or $k+1 = m+1$. In in first case, we have $k+1 = m \cdot 0 + k+1$ and therefore the least positive residue is $k+1$, implying $\sigma^1 (a_k)=a_{k+1}$. In the second case, the least positive residue is $1$ and $k=m$, so that $\sigma^1(a_k) = \sigma(a_m) = a_1$. In either case, however, the formula agrees with how $\sigma$ is defined to map the elements $\{a_1,...,a_m\}$.

I feel that the above is correct, but it could perhaps be stated more precisely, especially the line $\sigma^1(a_k) = \sigma(a_m) = a_1$.

Now I am trying to work on induction, but I am having a little trouble. Suppose that $\sigma^i(a_k)= a_{r}$, where $r$ is the least positive residue, holds for some $i$ (which $i$? How many?). Then $\sigma^{i+1}(a_k) = \sigma (\sigma^i(a_k))$. Since this holds for $i$, $\sigma^i(a_k) = a_r$. I am having trouble seeing what $\sigma$ does to $a_r$; i.e., what does $\sigma (a_r)$ equal?

 

[fresh_42]

Okay, I think I am starting to see now. Perhaps someone could help me with proving the theorem now. We will prove the theorem by induction. When $i=1$, we have the formula says $\sigma^1(a_k) = a_{k+1}$. Now, either $k+1 \in \{1,...,m\}$ or $k+1 = m+1$. In in first case, we have $k+1 = m \cdot 0 + k+1$ and therefore the least positive residue is $k+1$, implying $\sigma^1 (a_k)=a_{k+1}$. In the second case, the least positive residue is $1$ and $k=m$, so that $\sigma^1(a_k) = \sigma(a_m) = a_1$. In either case, however, the formula agrees with how $\sigma$ is defined to map the elements $\{a_1,...,a_m\}$.

I feel that the above is correct, ...

Yes.

... but it could perhaps be stated more precisely, especially the line $\sigma^1(a_k) = \sigma(a_m) = a_1$.

To me, it's fine.

Now I am trying to work on induction, but I am having a little trouble. Suppose that $\sigma^i(a_k)= a_{r}$, where $r$ is the least positive residue, holds for some $i$ (which $i$? How many?).

It holds for all numbers from $1$ to $i$. We simply pretend as if we had checked them all. And from that, we show, that it has to be also true for the next one, that is $i+1$.

Then $\sigma^{i+1}(a_k) = \sigma (\sigma^i(a_k))$. Since this holds for $i$, $\sigma^i(a_k) = a_r$.

Correct.

I am having trouble seeing what $\sigma$ does to $a_r$; i.e., what does $\sigma (a_r)$ equal?

Now you get a little bit lost. What you have (by induction hypothesis) is $\sigma^{i+1}(a_k) = \sigma (\sigma^i(a_k)) = \sigma (a_r) = \sigma^1 (a_r)$. You just have written it (in the line above my "correct"). But you know more about $r$. You constructed it with $i$ by doing $i$ additions $+1$ and reduced every of the $i$ results modulo $m$, step by step from $1$ until $i$. So is this the same as reducing the entire $r=k+i$ in one step instead? From here on, simply apply the same argument to $a_r$ as you did in the induction base for $a_k$.