1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Division Algorithm proof explanation

  1. Jan 7, 2013 #1
    This is taken from "Passage to Abstract Mathematics," Watkins and Meyer.

    "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.

    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]..."​

    (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!
  2. jcsd
  3. Jan 7, 2013 #2
    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)
  4. Jan 10, 2013 #3
    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 [itex]a + xb \geq 0[/itex], don't we already know that [itex]0\in S[/itex], or is that only if we're specifically told that [itex]a=0[/itex]?
    • Where does the [itex]a - (q+1)b[/itex] come from? I don't understand where [itex]q+1[/itex] comes from, specifically.
  5. Jan 10, 2013 #4
    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.
  6. Jan 10, 2013 #5


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    [itex]0\in S[/itex] if and only if [itex]\exists[/itex] x s.t. a+xb=0. Clearly that will only be the case if b divides a.
    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.
  7. Jan 11, 2013 #6
    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.

    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!
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook