Division Algorithm proof explanation

[SithsNGiggles]

This is taken from "Passage to Abstract Mathematics," Watkins and Meyer.

"Theorem 2.3.9 (Division Algorithm) If $a \in\mathbb{Z}$ and $b\in\mathbb{N}$, then there exist $q,r \in\mathbb{Z}$ such that $a = qb+r$ and $0 \leq r < b$.
Furthermore, for each $b\in\mathbb{N}$, this representation of $a$ is unique.

Proof.

Let $a\in\mathbb{Z}$ and $b\in\mathbb{N}$ be given, and let $S = \{ a + xb : x\in\mathbb{Z} \wedge a+xb\geq 0 \}$.

Note that there is an element in $S$. (If $a\geq 0$, pick $x=0$, so that $a\in S$; if $a<0$, pick $x=-a$, so that $a-ab = a(1-b) \in S$.) Thus, by the Well Ordering Principle, $S$ has a least element, which we denote by $r$. Since $r \in S, r=a-qb$ for some $q\in\mathbb{Z}$. By definition, $r \geq 0$.

Suppose that $r \geq b$. Then,
$a - (q+1)b = a - qb - b = r - b \geq 0$,
and $a-(q+1)b = r-b<r$, since $b>0$. This gives an element $r-b\in S$ which is strictly less than $r$, contradicting the minimality of $r$. Thus $r<b$. This yields the representation $a=qb+r$ with $0\leq r < b$..."​

(The rest of the proof concerns the uniqueness of the representation, which I understand somewhat.)

I was hoping someone could help explain the red text. My main questions are

• What is the advantage to using the set $S$? Or, in other words, why is this set used?
• What is the "Note that ... (If $a\leq 0$...)" saying? I don't really see what's going on here.
• How do we know that $r=a-qb$?

I think once these questions are addressed I'll be better equipped in understanding the proof overall. Thanks!

 

[Benn]

The bit in the parentheses is establishing that the the set S is nonempty. This needs to be known so that the well ordering principle can give us an element r to work with.

We know that r = a-qb since r is an element of S. You may be thinking "doesn't S have elements that look like a+xb?" It does, but we can put x = -q and have our desired representation.

I think that proof goes through every detail, and if I were you, I'd stare at it until it makes sense.

If you're not convinced that you need to use a set like S, try to write the proof without it. (I'm not suggesting you won't be able to)

 

[SithsNGiggles]

So I've been looking over this proof and throwing bits of it around in my head for a bit. I've got two more questions:

• Since $a + xb \geq 0$, don't we already know that $0\in S$, or is that only if we're specifically told that $a=0$?
• Where does the $a - (q+1)b$ come from? I don't understand where $q+1$ comes from, specifically.

 

[Benn]

So I've been looking over this proof and throwing bits of it around in my head for a bit. I've got two more questions:

• Since $a + xb \geq 0$, don't we already know that $0\in S$, or is that only if we're specifically told that $a=0$?
• Where does the $a - (q+1)b$ come from? I don't understand where $q+1$ comes from, specifically.

1: Let's look at the case when a=7 and b=2. Then a+xb = 7+2x. Keeping in mind that x is an integer, we see that there's no x that makes 7+2x = 0. So, in this case, 0 is not in S. Ask yourself when 0 will be in S.

----------

2: Still with a=7 and b=2, the division algorithm gives us 7= (3)2 + (1).

Let's say that you're fiddling around with this (without knowing the division algorithm). Maybe you stumble upon the expression 7 = (2)2 + (3) [note that here q=2 and r=3]. Now, 3 is not less than 2, so this seems to go against the division algorithm. Is this division algorithm wrong or can we fix it?

Well, we can just bump up q to 3 (=2+1). This is all that part of the proof is doing. It's establishing that we can find an r between 0 and b.

 

[haruspex]

[*]Since $a + xb \geq 0$, don't we already know that $0\in S$, or is that only if we're specifically told that $a=0$?

$0\in S$ if and only if $\exists$ x s.t. a+xb=0. Clearly that will only be the case if b divides a.

[*]Where does the $a - (q+1)b$ come from? I don't understand where $q+1$ comes from, specifically.

r is defined as the least element in S. q is then defined in terms of r, q+1 in terms of q, and finally a - (q+1)b in terms of that. The result is to show that if r >= b then we can construct a smaller member than r.

 

[SithsNGiggles]

1: Let's look at the case when a=7 and b=2. Then a+xb = 7+2x. Keeping in mind that x is an integer, we see that there's no x that makes 7+2x = 0. So, in this case, 0 is not in S. Ask yourself when 0 will be in S.

Okay, I see that now. I also reread the beginning and noticed that the proof starts off with letting a being given, so I think that answers my question.

2: Still with a=7 and b=2, the division algorithm gives us 7= (3)2 + (1).

Let's say that you're fiddling around with this (without knowing the division algorithm). Maybe you stumble upon the expression 7 = (2)2 + (3) [note that here q=2 and r=3]. Now, 3 is not less than 2, so this seems to go against the division algorithm. Is this division algorithm wrong or can we fix it?

Well, we can just bump up q to 3 (=2+1). This is all that part of the proof is doing. It's establishing that we can find an r between 0 and b.

Ah, alright. I see what's going on now, but I still need some time to digest all this information and put it all together. Thanks to both of you for the help!