# The Division Theorem and the Well Ordering Principle

I have been watching a video regarding proving the division theorem and I'm confused when proving the existence of the set of remainders.

The set for the remainders is specified as follows:

$$S$$= { a-nb | n $$\in$$ $$\mathbb{Z}$$ and $$a-nb \ge0$$ }

To see that it's non empty the author of the video provided the following statements:

if $$a$$ $$\ge 0$$, then $$a-0 \times b = a \in S$$

if $$a$$ $$< 0$$, then $$a - 2ab = a(1-2b)\in S$$

Now what I can't understand is why did the author of the video decide that he could just use n = 0 if he specified that $$n \in \mathbb{Z}$$ shouldn't have he specified that $$n \in \mathbb{N}$$ instead? Also, how can he just decided that n = 2a? if $$a < 0$$. I know that it makes the inequality true, but why can he just randomly choose such number?

• To show $a\!-\!b\Bbb Z \,\cap\, \Bbb N$ is nonempty we need to show that there is an integer $n$ with $a-nb\ge 0$. If $a\ge 0$ then $n=0$ works, else $a < 0$ and $n = 2a$ works. Precisely what is not clear abou that? Commented Apr 1, 2020 at 19:16
• @BillDubuque yes but what if $n$ is less than 0? Commented Apr 1, 2020 at 19:17
• $n$ ranges over $\Bbb Z$ so $n<0$ is permitted, We need to permit $n<0$ for the case $a<0\,$ (else $a-nb \le a < 0\,$ so it has no "remainders" $\ge 0,\,$ assuming the divisor $b > 0)\ \ \$ Commented Apr 1, 2020 at 19:22

Said intuitively: we have a set $$S\subseteq\Bbb Z$$ containing $$a$$ and closed under addition and subtraction of $$\,b,\,$$ and we seek to show that $$S$$ has an element $$\ge 0$$. If $$a\ge 0$$ then we are done. Else $$\,a<0\,$$ so adding a large enough value of $$b>0$$ will eventually yield a positive integer, indeed it is clear that it suffices to $$\,\rm\color{#0a0}{add}$$ $$\:-2ab = 2|a|b \ge 2|a| \color{#c00}{> |a|}$$ in order to $$\rm\color{#0a0}{\text{right-shift}\ \color{#c00}{a\ {\rm past}\ 0}},\,$$
The point is: we must prove $$S\cap \Bbb N$$ is nonempty in order to apply the well-ordering principle to it.
• @PapayaAutomata Before we can apply the well-ordering principle to a subset of $S\subset \Bbb N$ we need to show that $S$ is nonempty (else it has no elements so certainly no least element). Commented Apr 1, 2020 at 19:46
The smallest member of $$S$$ is going to be the remainder. Suppose that $$a=3$$ and $$b=-2$$; if $$-2=3q+r$$ with $$0\le r<3$$, then $$q=-1$$ and $$r=1$$, so we need to ensure that $$1\in S$$. But $$3-(-2)n=3+2n$$ is $$1$$ when $$n=-1$$, so we must allow negative values of $$n$$ in the definition of $$S$$ in order to be sure that $$S$$ actually will always contain the desired remainder.
There was nothing random about the choices $$n=0$$ and $$n=2a$$. To show that the set $$S$$ is non-empty, you need only find one number that you can prove belongs to $$S$$. When $$a\ge 0$$, taking $$n=0$$ does exactly that; similarly, when $$a<0$$, taking $$n=2a$$ does the trick. When $$a\ge 0$$ he could just as well have used $$n=-1$$, since $$a-(-1)b=a+b>0$$ when $$a\ge 0$$, but $$n=0$$ works and is a little simpler. Similarly, he could just as well have taken $$n=3a$$ when $$a<0$$, since $$a(1-3b)>0$$ when $$a<0$$.