Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Trouble setting up to prove unique factorization

  1. Aug 16, 2014 #1
    This lemma the book states, I can't make sense of it.

    Lemma: If a,b[itex]\in[/itex] [itex]Z[/itex] and b > 0, there exist q,r [itex]\in[/itex] [itex]Z[/itex] such that a = qb + r with 0 [itex]\leq[/itex] r < b.

    Proof: Consider the set of all integers of the form a-xb with x [itex]\in[/itex] [itex]Z[/itex]. This set includes positive elements. Let r = a - qb be the least nonnegative element in this set. We claim that 0[itex]\leq[/itex] r < b. If not, r = a - qb [itex]\geq[/itex] b and so 0[itex]\leq[/itex] a-(q+1)b<r, which contradicts the minimality of r.

    Can someone help explain this to me? Why can't a = 3, and b = 8. Then no q,r could exist so that r is less than b, right?
  2. jcsd
  3. Aug 16, 2014 #2
    Is this considered a textbook style question? Sorry, how can I move it? I just saw number theory and posted
  4. Aug 16, 2014 #3
    What is wrong with [itex] a=3 [/itex] and [itex] b=8[/itex]? Here you simply take [itex] q=0 [/itex] and [itex] r=3 [/itex] (there is no condition that says either q or r have to be nonzero) to get [itex] 3=(0)(8) +3 [/itex] and [itex] 0\leq 3< 8 [/itex] as required.
  5. Aug 16, 2014 #4
    Wow I'm quitting now

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook