Proof of Division AlgorithmDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/