Remainders and Euclidean Division

When we have two natural numbers $a$ and $b$ with $a>b$, we ask the question, "How much larger is $a$ than $b$?" First, some definitions:

Given integers $a,b$, we say that $a\mid b$, or $a$ divides $b$ if and only if there exists an integer $k$ such that $a=bk$.

An integer $k$ is a multiple of $n$ if and only if $n\mid k$.

We say "Given natural numbers $a,b$, we have $a$ is almost a multiple of $b$". However, we wish to find a more mathematically precise statement. The fuzzy part of the statement is the word 'almost'. We want to find an exact bound as to how far $a$ can be off from a multiple of $b$.

Division Algorithm: Given natural numbers $a$ and $b$, we can find integers $q$ and $r$ such that $a=bq+r$ and $0\leq r < b$.

This gives us a definite bound on how far off $a$ can be from a multiple of $b$. We said $a=bq+r$, so $a$ is close to $bq$, but can be off by $r$, which is less than $b$. This can be easily seen from the following diagram:

From this diagram and the division algorithm, we say that $a$ is almost a multiple of $b$, namely $3b$. However, $a$ is off of $3b$ by $r$. We know that $r<b$, or else we would have chosen $4b$ to be the multiple closest to $a$. This provides motivation for the proof.

Proof: Consider the set $\mathcal{S}=\left\{s\in\mathbb{Z}: s\geq 0 \text{ and }s=a-bx \text{ for some }x\in\mathbb{Z}\right\}$. Note that $a\in \mathcal{S}$ if we take $x=0$. Since this set is bounded from below, and is nonempty, we know it has a smallest element. Let $r=a-bq$ be the smallest element. Note that $a=bq+r$. Also, $r\geq 0$. Now we show that $r<b$.

For the sake of contradiction, suppose that $r\geq b$. However, we have $r-b\geq 0$, and $a-b(q+1)=a-bq-b=r-b$. That means $r-b\in\mathcal{S}$. However, we said that $r$ was the smallest element of $\mathcal{S}$, so we have a contradiction.

Thus, we have $r<b$. Hence, we have found $q,r$ such that $a=bq+r$ and $0\leq r < b$. $\Box$