The division algorithm states that if \(a\) and \(b\) are integers such that \(b \ge 0\), then there are unique integers \(q\) and \(r\) such that \(a = bq + r\) with \(0 \le r \lt b\).
Consider the set \(S\) of all integers of the form \(a-bk\) where \(k\) is an integer. Let \(T\) be the set of all nonnegative integers in \(S\). \(T\) will never be empty because there will always be some value for \(k\) such that \(a-bk \ge 0\). By the well-ordering property, \(T\) has a least element. Let's call the \(k\) in that element \(q\), so \(a-bq\) is the smallest element.
We set \(r=a-bq\), and these are the values for \(q\) and \(r\) specified in the theorem. We know that \(r \ge 0\) because \(a-bq\) exists in \(T\), which only contains nonnegative integers.
Is \(r \lt b\)? Assume \(r \ge b\), then:
However:
We have shown that \([a-b(q+1)]\) is nonnegative and greater than \([a-bq]\), which is a contradiction. Therefore, \(r \lt b\).
We know that \(q\) is unique because we chose \(k\) where \(a-bk\) is the smallest. Since \(r=a-bq\), then \(r\) too would be unique.