The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

Proof of Division Algorithm

Date: 11/13/97 at 10:02:51
From: James Lester
Subject: Proof of division algorithm

We are looking for a proof for the division algorithm:
a,b are positive integers, b does not equal 0;
there are unique integers q and r such that a = qb + r;
0 is less than or equal to r, r is less than modulus value of b.

The proof, which has so far evaded me, should be in the context of the 
course "Algebraic structures and number systems."

We need to 

1) prove the existence and uniqueness of q and r.

2) consider cases where 
   b is greater than or equal to 1
   b is less than or equal to -1

We also know that setX = {a-tb:t is a member of the integers, a-tb is 
greater than or equal to 0}.

The given strategy is to show X has a least element r (r = a-qb) and 
that r is less than or equal to modulus b, and greater than or equal 
to 0.

I hope you can help me.

Date: 11/13/97 at 14:45:04
From: Doctor Rob
Subject: Re: Proof of division algorithm

The strategy is an excellent one. 

The first thing you have to show is that X is not empty, that there is 
at least one integer in the set.  

Then X must have a least element. Let that element be r. Then since r 
is in X, it must have the form a - t*b for some t, which we call q.  

Then a = q*b + r. 

Now we have to show that 0 <= r < |b|. The first part is because r is 
in X, and every element of X is nonnegative, by definition.

Now suppose that r >= |b|.  Then r > s = r - |b| >= 0.  Now you can 
show (you fill in this part) that s is in X, but s is smaller than r.  
This is a contradiction to the choice of r as the smallest element of 
X. Thus the assumption that r >= |b| is false, and so r < |b|. That 
proves the existence of r, and hence of q.

To show uniqueness, suppose that q*b + r = a = q'*b + r', and 
0 <= r < |b|, and 0 <= r' < |b|. Then subtract to obtain 
(q-q')*b = r'-r. On the right side, 0 - |b| < r' - r < |b| - 0 (why?).  
Thus -|b| < (q-q')*b < |b|. 

Dividing by |b|, you get -1 < (q-q')*b/|b| < 1.  You must show that 
the quantity in the middle is an integer. If it is an integer, what 
must its value be? What does that say about q-q'? Substitute that 
into the equation in the second line of this paragraph, and you get 
r' - r = 0, so r = r'.  This proves uniqueness.

By using |b|, I have avoided considering the two cases. If you prefer 
to consider the two cases, in the first case, b >= 1, replace |b| with 
its equal b in the right places in the preceding proof. In the second 
case, b <= -1, replace |b| with -b, its equal in the right places in 
the preceding proof.

-Doctor Rob,  The Math Forum
 Check out our web site!   
Associated Topics:
College Modern Algebra

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.