1. Not finding help here? Sign up for a free 30min 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!

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




Similar Discussions: Proof of Altered Division Algorithm
  1. Division Algorithm (Replies: 3)

  2. Division algorithm (Replies: 13)

Loading...