I have several questions regarding the following proof of the division algorithm. I added my question in brackets at the parts that I don't really understand. Thank you very much for your help!
Division Algorithm:
Let a and b be integers with $b > 0$. Then there exists unique integers q and r with the property that $a = bq + r$, where $0 \leq r < b$.
Proof:
Let $a, b \in \mathbb{Z}$ with $b > 0$ and let us consider the set $S = \{a – bk \mid k \in \mathbb{Z} \text{ and } a – bk \geq 0 \}$ (with $a$ and $b$ fixed). [Q: we have considered this set as a basis for our proof. However, doesn't this mean that the proof only applies to that set? Why did we chose that set? Wouldn't this set need to have a special property that all integers share so that we can prove the theorem for all integers?]
First we prove the existence of $q$ and $r$.
Let us suppose $0 \in S$. Then $\exists k \in \mathbb{Z}$ where $a-bk = 0$. In that case, we have $a=bk$ and $b \mid a$. The required $q$ and $r$ are therefore $q = b \mid a$ and $r=0$. For $0 \in S$, we have proven the existence of $q$ and $r$.
Now we suppose $0 \notin S$ [Q: Do we separate both parts of the proof from each other? In other words, can we apply the results we got from the first part of the part to the second one? It doesn't really make sense since we can't have $0 \in S$ and $0 \notin S$ at the same time.]. $S$ is nonempty, because if $a>0$, we have $a-b \cdot 0$ (for $k=0$), which is $a$, i.e. $a \in S$, while if $a<0$, we can set $a-b(2a)$, which is also in $S$ ($a\neq0$ since $0\notin S$). Now because S is nonempty, we can apply the Well Ordering Principle, concluding that there exists a smallest member of $S$. Let that be $r$ and let $r = a – bq$ [Q: is this the $q$ we need to prove that it exists? Didn't we now just assume that it exists?]. Then we have $a = bq + r$ and $0 \leq r$ [Q: Didn't we assume that $0 \notin S$? That would mean that $r>0$? Did we set that because $r=0$ in the above example? However, both parts should be treated separately.]. We have proven that for $0 \notin S$, we also have $q$ and $r$, where $0 \leq r$. However, we still need to prove that $r < b$.
Let us assume for contradiction that $r \geq b$. Then we have $a – bq \geq b$ [Q: Is this because $r = a – bq$ in general or because we have set $r=a-bq$ in the above part of proof?]. Therefore, we have $a – bq – b \geq 0$, which is equivalent to $a – b(q + 1)$. Therefore, we have $a – b(q + 1) \geq 0$ (otherwise, $a – b(q + 1) \notin S$). But we also have $a – b(q+1) < a -bq$ (because $a – bq – b < a-bq$ and we have set $b>0$). However, we have set $r$, i.e. $a-bq$, to be the smallest member of $S$. That is a contradiction, so we have $r < b$.
Now we prove the uniqueness of $q$ and $r$.
Fur that purpose, let us suppose for contradiction that $\exists q, q', r, r' \in \mathbb{Z}$, such that $a=bq + r, \ \ 0 \leq r < b$ and $a=bq' + r', \ \ 0 \leq r' < b$. For convenience, we may also assume that $r' \geq r$. In that case, we have $bq + r = bq' + r'$ and therefore $b(q – q') = r' – r$. So $b$ divides $r'-r$ and therefore $0 \leq r'-r \leq r' < b$ (based on our assumptions). It follows that $r'-r = 0$ [Q: why?] and therefore $r'=r$ and $q'=q$.
Thank you very much for your help.
Best Answer
[Q: we have considered this set as a basis for our proof. However, doesn't this mean that the proof only applies to that set? Why did we chose that set? Wouldn't this set need to have a special property that all integers share so that we can prove the theorem for all integers?]
Note that $S$ is defined by $a$ and $b$ which are any integers such that $b>0$. Since this proof never gives exact values for $a$ and $b$, any integers can be put in their place (thus proving for all integers).
[Q: Do we separate both parts of the proof from each other? In other words, can we apply the results we got from the first part of the part to the second one? It doesn't really make sense since we can't have 0∈S and 0∉S at the same time.]
This is an example of cases in a proof. Think of it like an argument that has two possible starting places. You are trying to prove something for all $S$, but sometimes its hard to do that so you have to break it into parts. You first prove that its true if $0 \in S$, and then you prove that its true if $0 \not \in S$. The parts are not really connected, and don't reference each other, but since every $S$ must have $0$ or not have $0$, the statement must be true for every $S$ since its true for both cases.
[Q: is this the q we need to prove that it exists? Didn't we now just assume that it exists?]
Due to the Well Ordering Principle there must be a smallest member we call $r$, and since $r \in S$ it must be able to follow the "format" of $S$ which is $a−bk$. What we are doing here is refer to $k$ as $q$ since we know this will be the value we are looking for.
[Q: Didn't we assume that 0∉S? That would mean that r>0? Did we set that because r=0 in the above example? However, both parts should be treated separately.]
You are right that $r > 0$, but that also means that $r \geq 0$. All the proof is trying to show is that $r \geq 0$, so it doesn't need to keep the strict condition that $r > 0$.
[Q: Is this because r=a−bq in general or because we have set r=a−bq in the above part of proof?]
We have set $r=a−bq$, so $a-bq = r \geq b$ or $a-bq \geq b$.
[Q: why?]
Since $b$ divides $r' - r$ it must be true that $r' - r$ is a multiple of $b$. But, $r' - r < b$ and $r' - r \geq 0$, so it can only be a multiple of $b$ if $r' - r = 0$.