I'll give another proof, starting with a better statement of the lemma. I'll also use a bit more formal notation so ask if it's unclear.

Lemma: For all n, d in Z with d > 0 there exist unique q, r in Z such that n = d*q + r and 0 <= r < d.

Proof:

Let S = { s in Z : s >= 0 and exists q in Z with n = q*d + s }

I claim S is non-empty. To show that, you can take q = -|n|, and

s = n - q*d = n - (-|n|)d = n + |n|d

and since d in Z and d > 0 you have d >= 1, so

s = n +|n|d >= n + |n| >= 0

Now since S is a non-empty set of non-negative integers it contains a least element. Call that r.

From the definition of S, there's a corresponding q such that n = q*d + r. Also r >= 0. So now you need to prove r < d and q, r are unique.

From n = q*d + r you also have n = (q+1)*d + (r-d). So if 0 <= r-d then you'd have r-d in S, and r-d < r, contradicting the choice of r as the least element. That shows r-d < 0, so r < d.

Now say there was another r', q' satisfying n = q'*d + r' and 0 <= r' < d. If q = q', then r = n - q*d = n - q'*d = r'. If not, without loss of generality, assume q > q'. Subtracting 0 = (q-q')*d + (r-r'), or r'-r = (q-q')*d. Since q-q' > 0 you have q-q' >= 1, and r'-r >= d. But r' < d and r > 0, so r'-r < d, a contradiction. That proves q,r are unique.