Proving the unique remainder theorem

Question

Let $d∈\mathbb{Z}$, where $d \gt 0$ . Prove that for every $x ∈ \mathbb{Z}$ there is a unique remainder r ∈ $\mathbb{N}$ such that $x=qd+r$ where $q∈\mathbb{Z}$ and $0 \le r \lt d$.

Of course this is a very simple fact about remainders that we encounter early on in our math education. And it does seem intuitive, nevertheless I do have learn how to prove it, and how to do proofs in general. So far most of the 'proofs' I have done were actually verification than sophisticated proofs.

Now the proof is given as follows, and I put a number 1 next to the line I don't get.

To prove the uniqueness of r, assume $x=q_1d+r_1$ and $n=q_2d+r_2$, where $q_1$,$q_2$,$r_1$,$r_2$∈ $\mathbb{Z}$ and $0\le$ $r_1$, $r_2$ $\lt$ d.

Then $(q_1-q_2)d=r_2-r_1$

If $ r_1 \neq r_2$, we may assume $r_2 \gt r_1$.

This implies $r_2-r_1=md$, where $m\ge 1$ .

But this contradicts the fact that $r_2-r_1 \le r_2 \lt d$

To prove the existence of r, let $M=\{x-qd : q∈ \mathbb{Z}\}$

1. Then $ M ∩ \mathbb{N} \neq \varnothing $, I'm having trouble with this step.

and we let r be the first element in the subset M ∩ $\mathbb{N}$ of $\mathbb{N}$. Now r=x-qd for some q and we claim that $o \le r \lt d$. If $r \ge d$ then $r \gt r-d \ge 0$ and $r-d=x-(q+1)d ∈ M ∩ \mathbb{N}$. This contradicts that r is the first element in $ M ∩ \mathbb{N}$

Answer 1

In your uniqueness, you so far only showed that $r_1=r_2$. You still need to (quickly) show that also $q_1=q_2$.

Regarding $M\cap\Bbb N\ne\emptyset$: If $x\ge 0$, then certainly $x-0\cdot d\in \Bbb N$. And if $x<0$, then $x-x\cdot d=(-x)\cdot (d-1)\in\Bbb N$.

Answer 2

$$|dq_1-dq_2|=d\,|q_1-q_2|=|r_1-r_2|$$ we know $0\le r_1,r_2< d$, thus $$d\,|q_1-q_2|=|r_1-r_2|<d$$ in other words $$|q_1-q_2|<1$$

therefore $q_1=q_2$ because $q_1,q_2\in Z$.