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$