Use WOP to prove that for integers $a, m > 0$ there are integers $q, r \ge 0$, with $r \in \{0,1,2,\dots, m-1\}$ such that $a=qm+r$

Question

I just don't know where to start, I tried induction but that didn't work. I wrote a and m are greater than 0 and and we can say a is congruent to r(modm) but im notsure if thats correct. Any hints?

Answer 1

Let $a$ and $m$ elements of $\mathbb{Z}$ and $A=\{a-mk \mid k\in \mathbb{Z}\}\cap\mathbb{N}$. $A$ is a non empty subset of $\mathbb{N}$, then contain a least element, $r$ say. Since $r\in A$, there must be $q\in \mathbb{Z}$ so that $a-mq=r$. We now prove that $r<|m|$.

Let us assume that $r\geq |m|$, then $0\leq r-|m|=a-m(q+\epsilon), \epsilon=\pm 1 \in A$, contradiction because $r$ is minimal. This prove existence of $(q,r)$