If $x\notin\mathbb Q$, then $\left|x-\frac{p}{q}\right|<\frac{1}{q^2}$ for infinitely many $\frac{p}{q}$?

This appears on problem 1 of chapter 1 in Stein & Shakarchi's Real Analysis:

Given an irrational $x$, one can show (using the pigeon-hole principle, for example) that there are infinitely many fractions $p/q$, with relatively prime integers $p$ and $q$ such that $$\left|x-\frac{p}{q}\right|\leq\frac{1}{q^2}.$$ However, prove that the set of all $x\in\mathbb R$ such that there exist infinitely many fractions $p/q$, with relatively prime integers $p$ and $q$ such that $$\left|x-\frac{p}{q}\right|\leq\frac{1}{q^{3}} \text{ (or} \leq 1/q^{\epsilon+2})$$ is a set of measure zero.

The last part of the exercise is easy using the Borel-Cantelli theorem. However I have no idea why the first part is true.

• This answer shows that this is the case using a pigeon-hole argument. – robjohn Nov 9 '13 at 15:35

This is one of Dirichlet's classic arguments. For real $x$, for each $m$ in the range $1\le m\le N+1$, choose $n=n_m$ so that $mx-n_m\in [0,1)$ is the fractional part of $mx$. The $N+1$ choices of $m$ produce $N+1$ numbers $mx-n$ in $[0,1)$. Dividing the interval into $N$ subintervals of length ${1\over N}$, by the pigeon-hole principle some subinterval contains both $mx-n$ and $m'x-n'$ for some $1\le m'<m\le N+1$. That is, $${1\over N} \;\ge\; |(mx-n)-(m'x-n')| \;=\; |(m-m')x-(n-n')|$$ so $1\le q=m-m' \le N$ and $p=n-n'$ give $|qx-p|<{1\over N}\le {1\over q}$. Multiply through by $1/q$.
Meanwhile, the bound in your first part is achieved by all the convergents in the simple continued fraction for the irrational $x.$ See Theorem 5 at http://en.wikipedia.org/wiki/Continued_fraction#Some_useful_theorems