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.

Definition: Prime, Composite

We say an integer $n > 1$ is prime if its only factors are 1 and $n$. If $n$ has factors other than 1 and itself, then we say it is composite. The number 1 is neither prime nor composite.

This should be nothing new. However, what may be new is the process of checking to see if a number is prime. Of course, to see if some $n$ is prime, we could test to see if any of $2, 3, … n-2, n-1$ divide it. However, we don’t need to check any even number greater than 2, since if any other even number divides $n$, then so will 2. We can still throw away many potential factors, though – see if you can notice a pattern below: