# Least Positive Residue

1. Oct 24, 2016

### Bashyboy

1. The problem statement, all variables and given/known data
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$.

2. Relevant equations

3. 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)$?

2. Oct 24, 2016

### Staff: Mentor

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.

3. Nov 12, 2016

### 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\}$).

4. Nov 12, 2016

### vela

Staff Emeritus
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.

5. Nov 14, 2016

### 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?

6. Nov 14, 2016

### Staff: Mentor

Yes.
To me, it's fine.

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

Correct.
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$.