Results 1 to 3 of 3

Thread: Division Algorithm question

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

    Division Algorithm question

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

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

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

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

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

    Is this alright?

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

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    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: Feb 5th 2011, 12:18 PM
  2. The Division Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Feb 3rd 2011, 04:52 PM
  3. Division algorithm/mod
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Feb 13th 2010, 12:51 PM
  4. Division Algorithm
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Jan 18th 2009, 03:11 PM
  5. division algorithm
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: Sep 7th 2007, 01:39 PM

Search Tags


/mathhelpforum @mathhelpforum