Prove that $M \cap \mathbb{N} \neq\emptyset$, where $M = \{ x-qd \mid q \in \mathbb{Z} \}$

Question

I need to prove that $M \cap \mathbb{N} \neq\emptyset$, where $M = \left \{ x-qd \mid q \in \mathbb{Z} \right \}$, and $x,d \in \mathbb{Z}$, $ d > 0$

My attempt: Choose $x \geq 0$ then for all $qd \leq x$ we have that $(x - qd) \in \mathbb{N}$, and thus $M \cap \mathbb{N} \neq\emptyset$.

But I feel like this is not right, can anyone explain how to prove it?

Answer 1

As written, it appears that $x$ cannot be chosen. The statement is nonetheless true, for the following reason: let $x \in \mathbb{Z}$ and $d \in \mathbb{N}$. If $x > 0$ then $x \in \mathbb{N}$ and $x = x-0d \in M\cap \mathbb{N}$. If $x < 0$, we can take $q = 2x$ and so

$$ x - 2xd = x(1-2d) > 0 $$

because $x < 0$ and $1-2d < 0$. Thus, $x-2xd \in M \cap \mathbb{N}$. The remaining case is $x = 0$, for which you can take $q = 1$.

Answer 2

To brush away all the obfuscation:

For fixed $x,d\in \mathbb Z; d> 0$ then for any $q \in \mathbb Z$ then $x - qd \in \mathbb Z$. You are simply asked to prove that for some values of $q$ than $x - qd$ might be positive.

$x - qd > 0 \iff x > qd \iff \frac xd > q$.

So that that's it. For any integer $q < \frac xd$ then $x - qd\in M$ and $x - qd \in \mathbb Z$ and $x - qd > 0$ so $x-qd \in \mathbb N$ so $x-qd \in M \cap \mathbb N$ so $M\cap \mathbb N$ is not empty.

..... or .....

let $m = x - \lfloor \frac xd \rfloor d$ then $m > 0$ and $m \in \mathbb Z$ so $m \in \mathbb N$ and $m \in M$. So $m \in M \cap \mathbb N$ and $M \cap \mathbb N\ne \emptyset$.