Results 1 to 3 of 3

Math Help - Division Algorithm question

  1. #1
    Senior Member I-Think's Avatar
    Joined
    Apr 2009
    Posts
    288

    Division Algorithm question

    The division algorithm states
    b=aq+rwhere 0<r<a and b,a,q,r\in{Z}
    Prove r<\frac{b}{2}

    I shall attempt a proof by contradiction
    Assuming r>\frac{b}{2}
    Let r=\frac{mb}{n} where m<n<2m

    So
    b=aq+\frac{mb}{n}
    b-\frac{mb}{n}=b(1-\frac{mb}{n})=b(\frac{n-m}{n})=aq
    b=\frac{aqn}{n-m}

    Placing it into the original equation
     \frac{aqn}{n-m}=aq+r
    aqn=aqn-aqm+(n-m)r
    aq\frac{m}{n-m}=r

    And as \frac{m}{n}>\frac{1}{2} and m<n, then m>n-m
    So r>aq, but this is a contradiction to the division algorithm
    So r<\frac{b}{2}

    Is this alright?

    N.B.
    The case where r=\frac{b}{2} works similarly. You end up with r=aq, which is also a contradiction
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    The problem statement does not say that b >= a. If a > b, then q = 0 and r = b.

    Let r=\frac{mb}{n} where m<n<2m
    Are m and n integer? Why do they exist?

    I have not read your proof to the end, but I think there is an easier direct proof. Suppose b >= a. If a <= b/2, then r < a <= b/2. If a > b/2, then q = 1 and r = b - a < b/2.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member I-Think's Avatar
    Joined
    Apr 2009
    Posts
    288
    Sorry about that omission, but it is true that b>a>0 for this question.

    Yes, m and n are integers, they exist because any integer can be expressed as the fraction of another integer, and I chose to represent r as a fraction of b.

    But I understand your proof, it is easier.
    Thanks
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. The Division Algorithm 2
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 5th 2011, 12:18 PM
  2. The Division Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 3rd 2011, 04:52 PM
  3. Division algorithm/mod
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 13th 2010, 12:51 PM
  4. Division Algorithm
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 18th 2009, 03:11 PM
  5. division algorithm
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: September 7th 2007, 01:39 PM

Search Tags


/mathhelpforum @mathhelpforum