# 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$,^{1}^{1}For example, if $r=a+5b$ then $q=-5$. 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 |