Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
What have you tried? –  Chris Eagle Aug 2 '12 at 9:24
    
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
4  
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
show 2 more comments

1 Answer 1

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|improve this answer
add comment

Your Answer

 
discard

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.