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

Question

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$.

Answer 1

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|$.

Now, we have the following facts:

• 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$.