Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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
up vote 0 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.