# prove existence of integers $a,q$ which satisfy the following inequality

Let $x \in \mathbb{R}$ and integer $Q \geq 1$.

Prove: there exist integers $a$ and $1 \leq q \leq Q$ such that $|x - \frac aq | < \frac 1{qQ}$

any help would be appreciated!

-
i got $Q|xq-a| < 1$ but i don't see how can i continue. setting $a = \lceil x \rceil q$ is not a good idea... – taypen Aug 2 '12 at 9:26
Hint: Pigeonhole principle (with $Q$ pigeonholes). – Did Aug 2 '12 at 9:42
i don't understand how to use your hint... – taypen Aug 2 '12 at 9:57
This is a version of Dirichlet's theorem. See e.g. Wikipedia, Martin Klazar: Introduction to number theory or Wolfgang M. Schmidt. Diophantine approximation. Lecture Notes in Mathematics 785. Springer. p.1 – Martin Sleziak Aug 2 '12 at 11:31
See also here and here. – Martin Sleziak Aug 2 '12 at 11:36

What you want is $|qx - a| < \frac{1}{Q}$. For a given q, you can find an a satisfing this iff the fractional part of qx is either less than $\frac{1}{Q}$ or greater than $1-\frac{1}{Q}$. Now consider the Q candidates of q that you have. For each, compute the integer part of (fractional part of qa) times Q. This can have Q possible values from 0 to (Q-1). If each of these values is attained, then use the value of q which gives you 0 here. If not, by pigenhole principle there must be two candidates of q here which give you the same value here. Their difference will also be a candidate and will give 0 here, which makes it a valid candidate.