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.
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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search