Dirichlet’s approximation theorem

Theorem (Dirichlet, c. 1840): For any real number $\theta$ and any integer$n\ge 1$, there exist integers$a$ and $b$ such that $1\le a\le n$ and$\left|a\theta -b\right|\le \frac{1}{n+1}$.

Proof: We may assume $n\ge 2$.For each integer $a$ in the interval $[1,n]$, write$r_a=a\theta -[a\theta ]\in [0,1)$, where $[x]$ denotesthe greatest integer less than $x$. Since the $n+2$numbers $0,r_a,1$ all lie in the same unit interval, some twoof them differ (in absolute value) by at most $\frac{1}{n+1}$.If $0$ or $1$ is in any such pair, then the other element of thepair is one of the $r_a$, and we are done.If not, then $0\le r_k-r_l\le \frac{1}{n+1}$ for some distinct $k$and $l$. If $k>l$ we have $r_k-r_l=r_{k-l}$, since each side is in$[0,1)$ and the difference between them is an integer. Similarly,if , we have $1-(r_k-r_l)=r_{l-k}$. So, with $a=k-l$ or$a=l-k$ respectively, we get

$$\left|r_a-c\right|\le \frac{1}{n+1}$$

where $c$ is $0$ or $1$, and the result follows.

It is clear that we can add the condition $\gcd (a,b)=1$ to the conclusion.

The same statement, but with the weaker conclusion,admits a slightly shorter proof, and is sometimes also referred toas the Dirichlet approximation theorem. (It was that shorter proofwhich made the “pigeonhole principle” famous.) Also, the theoremis sometimes restricted to irrational values of $\theta$, with the(nominally stronger) conclusion.