Results 1 to 2 of 2

Math Help - Proving division algorithm

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    13

    Proving division algorithm

    Hi all,

    I'm having a tough time trying to go through the division algorithm proof.

    Theorem: Let (a,b) be two integers. Then there exists numbers q and r with a>= 0, 0=<r<=b such that a=bq+r.

    In class, my professor starts the proof by using cases, but I don't really understand why he does this.

    Case 1- If b>a then a=o*b+ a (0<a<b) q=0, r=a
    Case 2- if b=a then a=b*1+0, q=1, r=0
    Case 3- if b<a then a*1 ( I think my notes get cut off here since I was pretty confused in class).
    Does anyone know where he is trying to go with this? Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by jusstjoe View Post
    Hi all,

    I'm having a tough time trying to go through the division algorithm proof.

    Theorem: Let (a,b) be two integers. Then there exists numbers q and r with a>= 0, 0=<r<=b such that a=bq+r.

    In class, my professor starts the proof by using cases, but I don't really understand why he does this.

    Case 1- If b>a then a=o*b+ a (0<a<b) q=0, r=a
    Case 2- if b=a then a=b*1+0, q=1, r=0
    Case 3- if b<a then a*1 ( I think my notes get cut off here since I was pretty confused in class).
    Does anyone know where he is trying to go with this? Thanks
    Hi jusstjoe.

    The result won’t work if b=0. However I gather from your post that you want a and b to be both positive integers.

    Start by showing that the set \{n\in\mathbb N:nb\ge a\} is not empty. This will be true in Cases 1 and 2 with n=1. For Case 3, suppose to the contrary that nb<a for all natural numbers n. Then, in particular, ab<a \implies b<1 which is not possible if b is a positive integer. Hence there is a natural number n such that nb\ge a. Let q_0 be the smallest such natural number. The proof is completed by taking q=q_0-1 and r=a-bq-1.
    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. The Division Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 16th 2009, 12:45 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 Number Theory Forum
    Replies: 2
    Last Post: July 8th 2008, 08:33 PM

Search Tags


/mathhelpforum @mathhelpforum