Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proof of Altered Division Algorithm

  1. Jan 29, 2012 #1
    1. The problem statement, all variables and given/known data

    Show that, for positive integers [itex]a[/itex] and [itex]b[/itex], there exists unique integers [itex]q[/itex] and [itex]r[/itex] such that

    [itex]a = bq + r[/itex] and [itex]-b/2 < r \leq b/2[/itex].

    2. Relevant equations

    We can assume the standard division algorithm holds. That is, for integers [itex]a[/itex] and [itex]b[/itex], there exists unique integers [itex]q[/itex] and [itex]r[/itex] such that

    [itex]a = bq + r[/itex] and [itex]0 \leq r < b[/itex].

    Let [itex][\cdot][/itex] represent the floor function.

    3. The attempt at a solution

    Suppose [itex]a[/itex] and [itex]b[/itex] are positive integers. By the division algorithm, there exists unique integers [itex]q[/itex] and [itex]r[/itex] such that

    [itex]a = bq + r[/itex] and [itex]0 \leq r < b[/itex].

    At this point, I let [itex]r' = [b/2] - r[/itex]. Since [itex]0 \leq r[/itex], we have that [itex]-r \leq 0[/itex], which implies [itex][b/2] - r = r' \leq [b/2] \leq b/2[/itex] by the definition of the floor function. Also, since [itex]r < b[/itex], we see that [itex]-r > -b[/itex], which implies [itex][b/2] - r > [b/2] - b = [-b/2] \geq -b/2[/itex].

    This is where I get stuck. I have found an integer [itex]r'[/itex] that gives [itex]-b/2 < r' \leq b/2[/itex], but now I have to find an integer [itex]q'[/itex] to satisfy [itex]a = bq' + r'[/itex]. Any ideas?
     
    Last edited: Jan 29, 2012
  2. jcsd
  3. Jan 29, 2012 #2

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    The r' you have, will not work as the remainder of the altered algorithm. I don't know if that's what you intended or not.
     
  4. Jan 29, 2012 #3
    Right. The solution above doesn't work. I ended up choosing r' depending on what r - b was, which gives the desired result. Hopefully that helps anyone who has this problem in the future.
     
  5. Jan 29, 2012 #4

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Right !

    or ...
    Let r ' = r , q ' = q

    If r ' > b/2 then: r ' = r - b and q ' = q + 1 .
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook