This lemma the book states, I can't make sense of it.(adsbygoogle = window.adsbygoogle || []).push({});

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?

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Trouble setting up to prove unique factorization

**Physics Forums | Science Articles, Homework Help, Discussion**