# 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 $0\leq r and that such expression is unique.

Consider the numbers

 $\ldots,a-3b,a-2b,a-b,a,a+b,a+2b,a+3b,\ldots$

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 $r\geq 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 $0\leq r.

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

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

 $0

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

Title proof of division algorithm for integers ProofOfDivisionAlgorithmForIntegers 2013-03-22 13:01:11 2013-03-22 13:01:11 drini (3) drini (3) 4 drini (3) Proof msc 11A51