Need an assistance with a specific step of a specific Division Algorithm proof

I'm trying to wrap my head around a Division Algorithm's proof. That is,

Let $a, b \in \mathbb{Z}, a \neq 0$. Then there are unique $q,r \in \mathbb{Z}$ such that $b = qa + r, 0 \leq r < |a|$.

This is how I start(proving the existence of $q$ and $r$ :

Let's construct a set $S = \{ b-qa | q \in \mathbb{Z}, b-qa \geq 0 \}$

I'm going to use the well-ordering principle, but I'm having trouble with showing that $S$ is not empty.

If $b \geq 0$, then $b = b-0a \in S$

But i'm not sure how to prove the case when $b < 0$.

• @Shailesh I can't seem to understand two things. First of all, why? What if $a$ is not a positive integer? Secondly, can you write it in the form $|b|(a-1)=b-qa$? What is $q$ here? – Jxt921 Apr 17 '16 at 11:09
• I got that $|b|(a-1)$ is $b - ba = -b(a-1)$. That is, $q=b$. But $a-1$ is not necessary nonnegative. – Jxt921 Apr 17 '16 at 11:14

Let $q=-\operatorname{sgn}(a)(|b|+1)$. Then $qa=-\operatorname{sgn}(a)(|b|+1)a=-(\operatorname{sgn}(a)a)(|b|+1)$. Since $\operatorname{sgn}(a)a=|a|$, this equals $-|a|(|b|+1)=-|a||b|-|a|$. Therefore, $b-qa=b+|a||b|+|a|$.
• Since $a$ is a nonzero integer, $|a|\geq 1$.
• Since $|b|\geq -b$, $|b|+b\geq 0$.
Using these two inequalities, it follows that $b+|a||b|+|a|\geq b+|b|+1\geq 1$.