$P_k=[\frac{k-1}{m},\frac{k}{m})$, $k=1,\ldots,m.$, $q \in P_k$, prove that $nq \pmod 1 \in P_l$ for some $n \in \mathbb{N}$

I could not come up with a rigorous proof of the following fact, I'd be thankful if you could help me with this ( elementary) question.

Consider a partition $\Gamma_m$ of $[0,1)$ by sets $P_k=[\frac{k-1}{m},\frac{k}{m})$, $k=1,\ldots,m.$ Suppose $q \in P_k$ be a nonzero irrational number. For each $l\in\{1,\ldots,m\}$, Prove that there exists some $n\in \mathbb{N}$ such that $nq (mod \ 1) \in P_l$.

In fact, more is true: For irrational $q$, the sequence $\{nq\}=nq \bmod 1$ is uniformly distributed on $[0, 1)$, see for example equidistribution theorem here.

The result you wish to show is much weaker, and can easily be achieved with elementary means. Proof below.

Lemma: Let $q$ be irrational. Then $\exists n \in \mathbb{Z}^+$ s.t. either $0<\{nq\}<\frac{1}{m}$ or $1-\frac{1}{m}<\{nq\}<1$.

Proof: Consider the $m+1$ real numbers $0=\{0q\}, \{q\}, \{2q\}, \ldots , \{mq\} \in [0, 1)$. They are pairwise distinct. (otherwise $q$ would be rational, a contradiction) By Pigeonhole Principle applied to $P_0, \ldots P_{m-1}$, $\exists i$ s.t. $P_i$ contains two of them, which we call $\{uq\}$ and $\{vq\}$, $u<v$. Then either $\{vq\}>\{uq\}$, so $0<\{(v-u)q\}<\frac{1}{m}$, or $\{vq\}<\{uq\}$, so $1-\frac{1}{m}<\{(v-u)q\}<1$. In any case we may take $n=v-u$.

We proceed. Pick $n$ as in the lemma. If $0<\{nq\}<\frac{1}{m}$, then $\exists j \in \mathbb{Z}^+$ s.t. $0 \leq \frac{k-1}{m}<j\{nq\}<\frac{k}{m} \leq 1$, i.e. $\{(nj)q\} \in P_k$.

If $1-\frac{1}{m}<\{nq\}<1$, then $0<1-\{nq\}<\frac{1}{m}$, so $\exists j \in \mathbb{Z}^+$ s.t. $0 \leq \frac{m-k}{m}<j(1-\{nq\})<\frac{m-k+1}{m} \leq 1$, i.e. $j-1+\frac{k-1}{m}<j\{nq\}<j-1+\frac{k}{m}$, i.e. $\{(nj)q\} \in P_k$.

Thus we are done.

N.B. The equidistribution theorem may also be proved via elementary means, e.g. by Pigeonhole Principle; see here

I don't think it's true as stated anyway. Let m = 3, so the partition is [0,1/3), [1/3, 2/3), and [2/3, 1), and q = 1/2. It is true if 0 < q <1/m, because then q is less than the length of the intervals of the partition.

• sorry, $q$ must be irrational :-/ – the8thone May 19 '14 at 3:20