proof of division algorithm for integers

Let a,b integers (b>0). We want to express a=bq+r for some integers q,r with 0r<b and that such expression is unique.

Consider the numbers


From all these numbers, there has to be a smallest non negative one. Let it be r. Since r=a-qb for some q,11For example, if r=a+5b then q=-5. we have a=bq+r. And, if rb then r wasn’t the smallest non-negative number on the list, since the previous (equal to r-b) would also be non-negative. Thus 0r<b.

So far, we have proved that we can express a asbq+r for some pair of integers q,r such that 0r<b. Now we will prove the uniqueness of such expression.

Let q and r another pair of integers holding a=bq+r and 0r<b. Suppose rr. Since r=a-bq is a number on the list, cannot be smaller or equal than r and thus r<r. Notice that


so b divides r-r which is impossible since 0<r-r<b. We conclude that r=r. Finally, if r=r then a-bq=a-bq and therefore q=q. This concludes the proof of the uniqueness part.

Title proof of division algorithm for integers
Canonical name ProofOfDivisionAlgorithmForIntegers
Date of creation 2013-03-22 13:01:11
Last modified on 2013-03-22 13:01:11
Owner drini (3)
Last modified by drini (3)
Numerical id 4
Author drini (3)
Entry type Proof
Classification msc 11A51