1
$\begingroup$

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!

  • 0
    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...2012-08-02
  • 4
    Hint: Pigeonhole principle (with $Q$ pigeonholes).2012-08-02
  • 0
    i don't understand how to use your hint...2012-08-02
  • 0
    This is a version of Dirichlet's theorem. See e.g. [Wikipedia](http://en.wikipedia.org/wiki/Dirichlet%27s_approximation_theorem), Martin Klazar: [Introduction to number theory](http://kam.mff.cuni.cz/~klazar/ln_utc.pdf) or Wolfgang M. Schmidt. Diophantine approximation. Lecture Notes in Mathematics 785. Springer. [p.1](http://books.google.com/books?id=nAtBBPibjaYC&pg=PA1)2012-08-02
  • 0
    See also [here](http://math.stackexchange.com/questions/62565/what-is-your-favorite-application-of-the-pigeonhole-principle/62587#62587) and [here](http://math.stackexchange.com/questions/56045/approximation-of-irrationals-by-fractions/56054#56054).2012-08-02

1 Answers 1

0

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.