Question regarding proof of Euclid's Division Lemma

Question

Below is a proof from David Burton introductory text on number theory that I was reading.

Here the proof assumes that the smallest integer in the set S is r and then proceeds to prove that $0<=r<b$. My idea is that using the two conditions, a=bq+r and $0<=r<b$, we have to lock down on the uniqueness of q and r. But in the proof, through the assumption that r is the least element of S, we show $0<=r<b$. Why can we make this assumption that r is the least element in the set S? Why should this hold true?

Answer 1

The idea behind the proof is that one subtracts $b$ from $a$ as many times as possible with the condition that what remains be non-negative, i.e. be in $\mathbf N$. As a fundamental property of the natural numbers is that any non-empty subset has a smallest element, you're sure such an $r$ exists.

Answer 2

Given $b \ne 0$, each pair of integers $(q,r)$ such that $0\le r \lt |b|$ is associated with a unique integer $b \cdot q+r $

I demonstrate below by construction for the case $b \gt 0$:

$\mathbb{Z}= \{\dots,b\cdot(-1)+0,~~ b\cdot(-1)+1,~\dots,~~b\cdot(-1)+(b-1),\\ ~~~~~~~~~~~~~~~~~b\cdot(~~~0)+0,~~ b\cdot(~~~0)+1,~\dots,~~b\cdot(~~~0)+(b-1),\\ ~~~~~~~~~~~~~~~~~b\cdot(~~~1)+0,~~ b\cdot(~~~1)+1,~\dots,~~b\cdot(~~~1)+(b-1),~... \}$

I also demonstrate below by construction for the case $b \lt 0$:

$\mathbb{Z}= \{\dots,b\cdot(~~~1)+0,~~ b\cdot(~~~1)+1,~\dots,~~b\cdot(~~~1)+(b-1),\\ ~~~~~~~~~~~~~~~~~b\cdot(~~~0)+0,~~ b\cdot(~~~0)+1,~\dots,~~b\cdot(~~~0)+(b-1),\\ ~~~~~~~~~~~~~~~~~b\cdot(-1)+0,~~ b\cdot(-1)+1,~\dots,~~b\cdot(-1)+(b-1),~... \}$

Notice, that in each case the map between $(q,r)$ and $b \cdot q+r $ is a bijection.

So, given $b \ne 0$, for any $a\in \mathbb{Z}$ there exists a unique pair $(q,r)$, such that $0\le r \lt |b|$ and $a=b \cdot q+r $