# Remainder on Division is Least Positive Residue

Jump to navigation
Jump to search

## 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$

## Sources

- 1965: J.A. Green:
*Sets and Groups*... (previous) ... (next): $\S 2.5$. Congruence of integers: Example $39$