Định lý xấp xỉ Dirichlet (phép chia Farey)

Xét $Q+2$ số $0,\{\alpha\},\{2\alpha\},\dots,\{Q\alpha\},1$, trong đó $\{x\}$ là phần thập phân của $x$; tất cả đều nằm trong $[0,1]$. Chia $[0,1]$ thành $Q+1$ khoảng con bằng nhau, mỗi khoảng dài $1/(Q+1)$: $[0,\tfrac1{Q+1}), [\tfrac1{Q+1},\tfrac2{Q+1}),\dots$.

Ta có $Q+2$ số nhưng chỉ $Q+1$ khoảng con, nên theo nguyên lý chuồng bồ câu, hai trong số các số $\{j\alpha\}$ và $\{i\alpha\}$ (với $0\le i<j\le Q$, cho phép $i=0$ nên $\{i\alpha\}=0$) rơi vào cùng một khoảng con, do đó sai khác nhau ít hơn $1/(Q+1)$: $|\{j\alpha\}-\{i\alpha\}|<\tfrac{1}{Q+1}$.

Đặt $q=j-i$, vậy $1\le q\le Q$. Vì $\{j\alpha\}-\{i\alpha\} = (j\alpha - i\alpha) - (\lfloor j\alpha\rfloor - \lfloor i\alpha\rfloor) = q\alpha - a$ với số nguyên $a=\lfloor j\alpha\rfloor-\lfloor i\alpha\rfloor$, ta được $|q\alpha - a| < \tfrac{1}{Q+1}$, tức là $\left|\alpha-\dfrac aq\right| < \dfrac{1}{q(Q+1)}$.

Cuối cùng, nếu $\gcd(a,q)=d>1$, chia cả $a$ và $q$ cho $d$: phân số thu được có mẫu số còn nhỏ hơn và khoảng cách tới $\alpha$ bằng hoặc nhỏ hơn, nên ta có thể giả sử $\gcd(a,q)=1$ mà không mất tính tổng quát. Chứng minh hoàn tất; đây là lập luận chuồng bồ câu hữu hạn, mang tính dựng, không cần dựa vào bất kỳ ước lượng chưa được chứng minh nào.