The uniqueness of the Division Theorem The Division Theorem states, that
$$\forall a,b\in\mathbb{Z},b\neq0\colon\exists!q,r\in\mathbb{Z}\colon a=qb+r,0\le r<\vert b\vert$$
Usually, the proofs are divided into two parts: First a proof of the existence of these numbers and then a proof of their uniqueness. Looking at the (not formalized) proof: Considering
$$...,a-3b,a-2b,a-b,a,a+b,a+2b,a+3b,..$$
Selecting the smallest non-negative member of this sequence gives us an $r$ fulfilling the defining inequality and also gives us $q$ in terms of $r$ through the equality $r=a-qb$. This finishes the existence proof and then the uniqueness is shown using contradiction. However I don't understand why that is necessary.
Considering that $b\neq0$ we can say that $q_1\neq q_2\Rightarrow q_1b\neq q_2b$ and hence $a-q_1b\neq a-q_2b$ for any $q_1,q_2$. We conclude that all the elements of the sequence above are distinct. Choosing a least non-negative element of the sequence implies the Well-ordering principle is assumed.
It states that every subset of positive integers contains a least element, an element $s$ of the set $S$ so that $s\le x$ for all $x\in S$. When all elements are distinct however we know that no other $x=s$ exists, so the inequality becomes strict. This in turn implies the uniqueness of this least element, the uniqueness of $r$ and by $r=a-qb$ the uniqueness of $q$.
I would like to know whether the above reasoning is wrong and/or why the proof of the uniqueness using contradiction seems to always be included (I would consider observing that all elements are distinct easier and shorter than the whole contradiction proof).
 A: You have found $q$ and $0\leq r<b$ such that
$$a=bq+r$$
and this $r$ is characterized as the smallest non-negative element in the set $S=\{a-bq\mid q\in\mathbb{Z}\}$. 
The uniquenss of $r$ as the smallest positive element of $S$ is not enough. You also have to check that there is no other non-negative $s\in S$ with $0\leq s<b$ (such an $s$ need not be the smallest one). 
Ultimately, the proof boils down to showing that if $s\in S$ and $s>r$, then $s\geq r+b>b$ (so the inequality $0\leq s<b$ can't hold). You can't avoid this step.
A: We show here a direct proof of uniqueness.
In this exposition all numbers will belong to the ring of integers $\Bbb Z$, and three numbers $b, r, s \in \Bbb Z$ are related by
$\tag 1 b \ne 0$
$\tag 2 0 \le r \lt |b|$
$\tag 3 0 \le s \lt |b|$
The following can be proved without using reductio ad absurdum, and is left as an exercise.
$$\tag 4 r = nb + s \; \text{ If And Only If } \; [n = 0 \; \text{ and } \; r = s]$$
Now assume that 
$$\tag 5 a=bq_1+r \text{ and } a = bq_2+s$$
is true.
Consider the statements
$$\tag 6 a+b=b(q_1+ 1) + r \text{ and } a+b = b(q_2+1)+s$$
$$\tag 7 a-b=b(q_1- 1) + r \text{ and } a-b = b(q_2-1)+s$$
Then the statements $\text{(5)-(7)}$ are all equivalent.
So we can construct a 'truth chain', to other statements
$$\tag 8 \hat a= b \hat{ q_1}+s \text{ and } \hat a = b \hat{ q_2}+s$$
and we can transform $q_1$ to $0$, so that $\hat{ q_1} = 0$ in $\text{(8)}$,
$$\tag 9 \hat a= r \text{ and } \hat a = b \hat{ q_2}+s$$
But then 
$\tag {10} r = b\hat{ q_2}+s$ and by $\text{(4)}$, $\,r = s$ and $\hat{q_2} = 0$.
There are two ways you prove that $q_1 = q_2$:
Using $\text{(5)}$, $bq_1 = bq_2$ and $q_1 = q_2$ follows.
Since $\hat{ q_2} = \hat{ q_2}$ and the transforms $\text{(6)/(7)}$ are $\text{1:1}$ "on the q's", it must be true that $q_1 = q_2$.
