Question regarding the Division Algorithm Proof 
Division Algorithm:


Let $a$ and $b$ be integers with $b>0$. Then there exists unique integers $q$ and $r$ such that $a = bq +r$ with $0 \le r < b$.

I have a couple of questions regarding the proof and was hoping that someone might be able to explain them to me.
Proof:

1. Existence:


Let $S=\{x \in \mathbb Z : x=a-bn ~ \text{for some } n \in \mathbb Z \}$ and let $S'$ be the set of nonnegative integers in $S$, then $S' \neq \emptyset$.


(WHY CAN WE SAY FOR CERTAIN THAT $S' \ne \emptyset$ ?)


If $0 \in S'$ then $S'$ contains a least element $0 = a - bq$ for some $q \implies a = bq + 0$ with $r=0$. So $a = bq + r$ with $0 \le r <b$, the equality of $0 \le r$ in this case.


If $0 \not\in S'$ then $S'$ contains a least element $r = a - bq \implies a = bq +r$ with $r>0$. Furthermore \begin{align}r-b &= a - bq - b \\&= a - b(q+1)\end{align}
Hence $r -b \in S$. Since $r$ is the least element in $S'$ and $r-b < r$, it follows that $r-b < 0 \implies r<b$.


So in both cases $a = bq + r$ with $0 \le r < b$.


2. Uniqueness:


Now suppose $a = bq_1 + r_1$ and $a = bq_2 + r_2$ where $0 \le r_1, r_2 < b$.


Without loss of generality, assume $r_1 \le r_2$. Now \begin{align}0 \le r_2 - r_1 &= a-bq_2 - (a - bq_1) \\ &=b(q_1 - q_2)\end{align}
This means that $r_2 - r_1$ is a nonnegative multiple of $b$ that is less than $b$. So \begin{align}r_2 - r_1 &= 0 \implies r_2 = r_1\end{align}
(WHY IS $r_2 - r_2 = 0$)? - I simply cannot seem to understand why?


Hence $b(q_1 - q_2) = 0 \implies q_1 - q_2 = 0 \implies q_1 = q_2$.

 A: $r_2-r_1=0$ because a positive multiple of $b$ is at least equal to $b$, and this one is smaller. As it is nonnegative, it must be $0$.
A: For the first question: $S'$ is not empty because if you let $n<0$ (it is an integer), then $-bn$ is positive.  By choosing $n$ large, we know that $a-bn$ is positive (even if $a$ is negative, if we choose $|n|$ very large, then $-bn$ will cancel out the $a$.
For the second question: You've proved that 

* $r_2-r_1\geq 0$.

* The smallest element of $S'$ is less than $b$.

* $r_2-r_1=b(q_1-q_2)$, so $r_2-r_1$ is a multiple of $b$.
Then, you know that $r_2-r_1$ is a positive multiple of $b$.  What are the positive multiples of $b$ - they are $b,2b,3b,\cdots$ all of which are greater than or equal to $b$.
Finally, since, by assumption, $r_2<b$, we know that $r_2-r_1$ is even smaller, so $r_2-r_1<b$.  Therefore, $r_2-r_1$ is a nonnegative multiple of $b$ that is smaller than $b$ (but there are no nonzero multiples of $b$ that are smaller than $b$).  This leaves only $r_2-r_1=0$.
