Results 1 to 4 of 4

Math Help - Division Algorithm

  1. #1
    Newbie
    Joined
    Dec 2008
    From
    Philadelphia
    Posts
    24

    Division Algorithm

    Can someone prove the division algorithm for me? I really don't understand the proof the way my professor does it. He uses induction or something, I really don't know and no site explains it clearly enough for me. Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member vincisonfire's Avatar
    Joined
    Oct 2008
    From
    Sainte-Flavie
    Posts
    469
    Thanks
    2
    Awards
    1
    Do you mean Euclidian Algorithm?
    Or the proof that a = bq +r with q and r uniquely determined?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2008
    From
    Philadelphia
    Posts
    24
    Yes that one, where q and r exist. I'm not worry about them being unique yet.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member vincisonfire's Avatar
    Joined
    Oct 2008
    From
    Sainte-Flavie
    Posts
    469
    Thanks
    2
    Awards
    1
    For simplicity, assume b > 0. Very similar arguments prove the case b < 0.
    Consider the set S = {a − bx : x ∈ Z, a − bx ≥ 0}.
    It is the set of all non-negative “residues”. We claim that S is a non-empty set. Indeed, if a > 0 take x = 0 and it follows that a ∈ S. If a < 0 take x = a and a − bx = a(1 − b) ≥ 0 (because b > 0 and so b ≥ 1). That is, a(1 − b) ∈ S. Since S is a non-empty subset of N, it follows that S has a minimal element r = a − bq for some q . Then r < b; otherwise, 0 ≤ r − b = a − b(q + 1) is an element of S as well and smaller that r , which is a contradiction. It follows that a = bq + r , 0 ≤ r < b.
    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. Division Algorithm.....
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: June 26th 2010, 06:53 AM
  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 Number Theory Forum
    Replies: 2
    Last Post: July 8th 2008, 08:33 PM
  5. division algorithm
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: September 7th 2007, 01:39 PM

Search Tags


/mathhelpforum @mathhelpforum