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?

  • $\begingroup$ 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? $\endgroup$ Commented Apr 1, 2020 at 19:16
  • $\begingroup$ @BillDubuque yes but what if $n$ is less than 0? $\endgroup$
    – KetDog
    Commented Apr 1, 2020 at 19:17
  • $\begingroup$ $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)\ \ \ $ $\endgroup$ Commented Apr 1, 2020 at 19:22

2 Answers 2


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.

  • $\begingroup$ OK, so in the well ordering prince we need to find just one element and we are done?. I was getting confused and thought we had to prove for all elements. $\endgroup$
    – KetDog
    Commented Apr 1, 2020 at 19:45
  • 1
    $\begingroup$ @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). $\endgroup$ 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$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .