Division Algorithm

Given two integers $a$ and $b$ , with $b \neq 0$ , there exist unique integers $q$ and $r$ such that $$a=bq+r$$ and $0 \leq r < | b |$ , where $| b |$ is the absolute value of $b$ .

$a$ is called the dividend,
$b$ is called the divisor,
$q$ is called the quotient,
$r$ is called the remainder

function divide_unsigned(A,B)
    if B = 0 then error(DivisionByZero) end
    R := A
    Q := 0
    while R ≥ B do
        R := R − B
        Q := Q + 1
    end
    return (Q, R)
end

Proof

Existence

Suppose (without loss of generality) that $b > 0$

There exist integers $q_{1}, r_{1} \geq 0$ such that $a = b q_{1} + r_{1}$ :

$a \geq 0$ :
$q_{1} = 0$ and $r_{1} = a$
$a < 0$ :
$q_{1} = a$ and $r_{1} = a - a b$

Let $q$ and $r$ be such integers.
If $r \geq b$ :
$a = b (q + 1) + (r - b)$ , with $0 \leq r - b < r$ ,
so $r$ is not minimal

Then the algorithm for finding a minimal $r$ is:

Start with $q = 0$
Increment by 1 until $a - b q < b$

Uniqueness

Let $q^{'}, r^{'}$ be a quotient and remainder pair.

By definition,

\begin{array}{r} 0 \leq r < | b | \\ 0 \leq r^{'} < | b | \end{array}

Thus, $| r^{'} - r | < | b |$ .

By definition,

\begin{aligned} a & = b q + r \\ a & = b q^{'} + r^{'} \end{aligned}

Setting these equal to each other,

\begin{aligned} b q + r & = b q^{'} + r^{'} \\ b (q - q^{'}) & = r^{'} - r \end{aligned}

so $b$ is a divisor of $(r^{'} - r)$ .

However, as established, $| r^{'} - r | < | b |$ ;
then, necessarily, $r^{'} - r = 0$ and $q - q^{'} = 0$ ,
so $r^{'} = r$ and $q^{'} = q$ .

QED.