The Division Algorithm Proof
For any integers
\[a, \; b, \; b \gt 0\]
, there exist unique integers \[q, \; r\]
such that \[a=bq+r, \; 0 \le r \le b\]
ProofConsider the set of integers
\[S=\{a-bn /gt 0: n \in \mathbb{Z} \}\]
.\[S\]
is not empty as \[b \gt 0 \rightarrow a-bn \gt \]
if \[n \lt 0\]
Either
\[0 \in S\]
and \[0\]
is the smallest member of \[S\]
or \[S\]
is a non empty set of positive integers so by the Well Ordering Principle again, \[S\]
has a smallest element. In either case, there exists an integer \[q\]
such that \[a-bq=r\]
is the smallest element of \[S\]
. Hence there are integers \[q, \; r\]
such that \[a=bq+r, \; \le r\]
.If
\[r \gt b\]
then \[r-b \gt 0\]
so \[r-b=a-bq-b=a-b(q+1)\]
and \[r-b\]
is a smaller element of \[S\]
than \[r\]
which contradicts the definition of \[r\]
above, so \[r \lt b\]
.Suppose the now there exist
\[r, \; r'\]
satisfying\[a=bq+r, 0 \le r \lt b\]
\[a=bq'+r', 0 \le r' \lt b\]
Subtraction gives
\[0=b(q-q')+ r-r' \]
.If
\[q=q'\]
the \[r=r'\]
and the expressions are the same.Suppose then
\[q \neq q'\]
. Assume \[q \gt q' \rightarrow q-q' \gt 0\]
, then \[r'-r=b(q-q') \ge b \times 1 =b \]
contradiction that \[0 \le r, \; r' \lt b\]
.Therefore
\[b, \; q\]
are unique. 
