|
Theorem (Dirichlet, c. 1840): For any real number and any integer , there exist integers and such that
and
.
Proof: We may assume . For each integer in the interval , write
, where denotes the greatest integer less than . Since the numbers all lie in the same unit interval, some two of them differ (in absolute value) by at most
. If 0 or is in any such pair, then the other element of the pair is one of the , and we are done. If not, then
for some distinct and . If we have
, since each side is in and the difference between them is an integer. Similarly, if , we have
. So, with or respectively, we get
where is 0 or , and the result follows.
It is clear that we can add the condition
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 , with the (nominally stronger) conclusion
.
|