- #1

SithsNGiggles

- 186

- 0

"

**Theorem 2.3.9 (Division Algorithm)**

*If [itex]a \in\mathbb{Z}[/itex] and [itex]b\in\mathbb{N}[/itex], then there exist [itex]q,r \in\mathbb{Z}[/itex] such that [itex]a = qb+r[/itex] and [itex]0 \leq r < b[/itex].*

Furthermore, for each [itex]b\in\mathbb{N}[/itex], this representation of [itex]a[/itex] is unique.

Furthermore, for each [itex]b\in\mathbb{N}[/itex], this representation of [itex]a[/itex] is unique.

*Proof.*

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

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

Suppose that [itex]r \geq b[/itex]. Then,

[itex]a - (q+1)b = a - qb - b = r - b \geq 0[/itex],

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

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

Suppose that [itex]r \geq b[/itex]. Then,

[itex]a - (q+1)b = a - qb - b = r - b \geq 0[/itex],

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

(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 [itex]S[/itex]? Or, in other words, why is this set used?
- What is the "Note that ... (If [itex]a\leq 0[/itex]...)" saying? I don't really see what's going on here.
- How do we know that [itex]r=a-qb[/itex]?

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