# Remainder on Division is Least Positive Residue

## Theorem

Let $a, b \in \Z$ be integers such that $a \ge 0$ and $b \ne 0$.

Let $r$ be the remainder resulting from the operation of integer division of $a$ by $b$:

$a = q b + r, 0 \le r < \size b$

Then $r$ is equal to the least positive residue of $a \pmod b$.

## Theorem

By definition of least positive residue:

$a = q b + r \iff r \equiv a \pmod b$

for some $q \in \Z$.

By the Division Theorem, there exists a $q$ such that:

$0 \le r < \size b$

which is precisely the definition of the least positive residue of $a \pmod b$.

$\blacksquare$