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!