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?
 A: 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.
A: 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.
If you needed further help I'd explain it in more details.
