Dividing with a remainder

1. 01Let $S$ be the set of non-negative integers of the form $a - b\cdot q$, over all integers $q$.Define $S$
2. 02$S$ is not empty: taking $q = -|a|$ gives $a + b\cdot |a| \ge 0$.Nonempty
3. 03Let $r$ be the smallest element of $S$, say $r = a - b\cdot q$.Smallest element
4. 04If $r \ge b$, then $r - b = a - b\cdot (q + 1)$ is in $S$ and smaller than $r$, a contradiction.Contradiction
5. 05So $0 \le r < b$, and $a = b\cdot q + r$. $\blacksquare$Conclusion