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.
James.

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!  http://mathforum.org/dr.math/