1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Least Positive Residue

  1. Oct 24, 2016 #1
    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. jcsd
  3. Oct 24, 2016 #2

    fresh_42

    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.
     
  4. Nov 12, 2016 #3
    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\}##).
     
  5. Nov 12, 2016 #4

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    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.
     
  6. Nov 14, 2016 #5
    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?
     
  7. Nov 14, 2016 #6

    fresh_42

    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##.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Least Positive Residue
  1. Poles and residues (Replies: 12)

  2. Find the residue for (Replies: 8)

Loading...