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
    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.