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 and that such expression is unique.

Consider the numbers

$$\mathrm{\dots },a-3b,a-2b,a-b,a,a+b,a+2b,a+3b,\mathrm{\dots }$$

From all these numbers, there has to be a smallest non negative one. Let it be $r$. Since $r=a-qb$ for some $q$, we have $a=bq+r$. And, if $r\ge b$ 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 .

So far, we have proved that we can express $a$ as$bq+r$ for some pair of integers $q,r$ such that . Now we will prove the uniqueness of such expression.

Let $q^{\prime }$ and $r^{\prime }$ another pair of integers holding $a=b{q}^{\prime }+r^{\prime }$ and . Suppose $r\ne r^{\prime }$. Since $r^{\prime }=a-b{q}^{\prime }$ is a number on the list, cannot be smaller or equal than $r$ and thus . Notice that

so $b$ divides $r^{\prime }-r$ which is impossible since . We conclude that $r^{\prime }=r$. Finally, if $r=r^{\prime }$ then $a-bq=a-b{q}^{\prime }$ and therefore $q=q^{\prime }$. 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