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

  • $\begingroup$ @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? $\endgroup$ – Jxt921 Apr 17 '16 at 11:09
  • $\begingroup$ I got that $|b|(a-1)$ is $b - ba = -b(a-1)$. That is, $q=b$. But $a-1$ is not necessary nonnegative. $\endgroup$ – 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|$.

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

  • 1
    $\begingroup$ Very nice! Thank you a lot. $\endgroup$ – Jxt921 Apr 17 '16 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.