I assume we’re just talking about positive integer division here. If so, let’s take a minute to prove that it works.

Take any two integers a and b with a > b. We want to prove that there are integers q and r, 0 < r < b, such a = qb + r. Obviously, a = nb + (a - nb) for any integer n. Now, the integers are Archimedean, which means that for any integers a and b, there is an integer n such that a < nb. This implies that there is a least such n, which we’ll denote [symbol]n[/symbol]. In that case, a = [symbol]n[/symbol]b + (a - [symbol]n[/symbol]b), and a - [symbol]n[/symbol]b < b. If not, a > ([symbol]n[/symbol] + 1)b, which contradicts our assumption that a < [symbol]n[/symbol]b.

So that’s the existence proof. Now, let’s assume that for some pair of integers (a, b) (a > b) that there are two sets of integers, (q[sub]1[/sub], r[sub]1[/sub]) and (q[sub]2[/sub], r[sub]2[/sub]), such that a = q[sub]1[/sub]b + r[sub]1[/sub], a = q[sub]2[/sub]b + r[sub]2[/sub], 0 < r[sub]1[/sub] < b, and 0 < r[sub]2[/sub] < b. Can this be?

I think it’s obvious that q[sub]1[/sub]b + r[sub]1[/sub] - (q[sub]2[/sub]b + r[sub]2[/sub]) = 0, or (q[sub]1[/sub] - q[sub]2[/sub])b + (r[sub]1[/sub] - r[sub]2[/sub]) = 0. This implies that (q[sub]1[/sub] - q[sub]2[/sub])b = r[sub]2[/sub] - r[sub]1[/sub].

Without losing generality, we can assume that r[sub]1[/sub] < r[sub]2[/sub], which implies that 0 < r[sub]1[/sub] < r[sub]2[/sub] < b, which implies that 0 < r[sub]2[/sub] - r[sub]1[/sub] < b - r[sub]1[/sub] < b.

With r[sub]2[/sub] - r[sub]1[/sub] > 0, it follows that q[sub]1[/sub] - q[sub]2[/sub] > 0. We can assume that q[sub]1[/sub] != q[sub]2[/sub], which implies that q[sub]1[/sub] - q[sub]2[/sub] > 1 (as there are no integers with a difference smaller than 1). Then we have that (q[sub]1[/sub] - q[sub]2[/sub])b > b (I trust this is obvious). Take that in conjunction with our result that r[sub]2[/sub] - r[sub]1[/sub] < b, and you have a contradiction.

The proof for non-positive integers is similar enough that the reader should be able to supply it.