Thread: Division Algorithm

Can someone prove the division algorithm for me? I really don't understand the proof the way my professor does it. He uses induction or something, I really don't know and no site explains it clearly enough for me. Thanks

Do you mean Euclidian Algorithm?
Or the proof that with q and r uniquely determined?

Yes that one, where q and r exist. I'm not worry about them being unique yet.

For simplicity, assume b > 0. Very similar arguments prove the case b < 0.
Consider the set S = {a − bx : x ∈ Z, a − bx ≥ 0}.
It is the set of all non-negative “residues”. We claim that S is a non-empty set. Indeed, if a > 0 take x = 0 and it follows that a ∈ S. If a < 0 take x = a and a − bx = a(1 − b) ≥ 0 (because b > 0 and so b ≥ 1). That is, a(1 − b) ∈ S. Since S is a non-empty subset of N, it follows that S has a minimal element r = a − bq for some q . Then r < b; otherwise, 0 ≤ r − b = a − b(q + 1) is an element of S as well and smaller that r , which is a contradiction. It follows that a = bq + r , 0 ≤ r < b.