3.1: Division Algorithm – Number Theory

3.1: Division Algorithm

Jump to:

To start the chapter, we will formalize a result that you’ve been familiar with since the start of your mathematics career. It may seem trivial and unnecessary, but as you will see later, the formal statement of this theorem will aid us in deriving more complicated results.

Recall, when dividing one integer $a$ by another integer $b$, either $b$ evenly divided $a$, or there was some remainder left over, where the remainder was less than $b$. For example, when dividing 13 by 5, we have a remainder of 3.

Definition: Division algorithm

If $n, d$ are positive integers such that $n \geq d$, then it is possible to find non-negative integers $q, r$ such that $n = dq + r$, where $r < d$.

In the above statement:

It turns out that finding $q$ and $r$ is relatively easy.

$q = \lfloor \frac{n}{d} \rfloor$

$r = n - dq$

For example, we can represent the division of 13 by 5 by the expression $13 = 5 \cdot 2 + 3$.

If the remainder is 0, then we say that $d$ “divides” $n$, and that $d$ is a factor of $n$. This is represented by the notation

$d \big| n$

Read on to see applications of this result.