# How do you prove the division theorem?

Okay, the division theorem states that there exist natural numbers $a,b,q,r$ such that $b=aq+r$ with the condition that $a>0$ and $0<=r<a$.

This is pretty much common sense. Though, how am I suppose to prove it? Is it possible to prove the theorem by giving examples?

• No, it says that for any positive natural numbers $a$ and $b$, there exist natural numbers $q$ and $r$, etc.
– MJD
Commented Aug 7, 2013 at 18:13
• In elementary number theory textbooks you'll find proofs by induction. Commented Aug 7, 2013 at 18:13
• Thanks guys! Any good number theory starter books suggestions? Commented Aug 7, 2013 at 18:17
• It may be common sense, but it fails in some "integer-like" structures. As for a proof, let $R$ be the set of non-negative integers of the form $b-ax$, where $x$ ranges over the integers. It is easy to see that $R$ is non-empty. Let $r$ be the smallest element of $R$. This will turn out to be the $r$ we seek. Commented Aug 7, 2013 at 18:27

No, it's not possible to prove a theorem by giving examples. Set $S=\{b-aq>0: b,q \in \mathbb{Z} , a\in \mathbb{N} \}$ Prove that $S \neq \emptyset$. Since $S$ is a non-empty subset of natural numbers it has a least element by the well-ordering principle. Let the least element of $S$ be $r$. Prove that if $r > a$ we'll have a contradiction. This proves that $r \leq a$, but the case $r=a$ can be remedied by substituting $q+1$ instead of $q$ and setting $r=0$. Now prove that $r$ and $q$ are unique.
Let me rephrase your statement of the division algorithm slightly. For any integers $a>0$ and $b\ge 0$ there exist integers $q\ge 0$ and $0\le r < a$ for which $$b = aq+r$$ Clearly, there will always be $q, r$ satisfying the equation above: just let $q=0, r=b$. The difficulty is showing that you can find a $r<a$. The cute way to do this is to assume that there is no such $r$ with $r<a$. Among all the $(q, r)$ values that satisfy the equation, let $r'$ be the smallest such value. Such a value exsits, since we assume $r'$ is bounded below by zero. Now argue to a contradiction by showing that you can find a smaller $r''<r'$. Hint: if $(q, r')$ is a solution with $r'\ge a$, then $(q+1, r'-a)$ is also.