# 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]$ denotes
the greatest integer less than $x$. Since the $n+2$
numbers $0,{r}_{a},1$ all lie in the same unit interval, some two
of 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 the
pair 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 $\mathrm{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 to
as the Dirichlet approximation theorem^{}. (It was that shorter proof
which made the “pigeonhole principle^{}” famous.) Also, the theorem
is sometimes restricted to irrational values of $\theta $, with the
(nominally stronger) conclusion
$$.

Title | Dirichlet’s approximation theorem |
---|---|

Canonical name | DirichletsApproximationTheorem |

Date of creation | 2013-03-22 13:15:37 |

Last modified on | 2013-03-22 13:15:37 |

Owner | Koro (127) |

Last modified by | Koro (127) |

Numerical id | 7 |

Author | Koro (127) |

Entry type | Theorem |

Classification | msc 11J04 |

Synonym | Dirichlet approximation theorem |

Related topic | IrrationalityMeasure |