[proofplan]
We first prove the finite denominator bound by applying the pigeonhole principle to the $N+1$ fractional parts of $0\theta,1\theta,\dots,N\theta$ after partitioning $[0,1)$ into $N$ half-open intervals of equal length. Two fractional parts in the same interval differ by less than $1/N$, and subtracting the corresponding integer parts produces integers $p$ and $q$ with $1 \le q \le N$. For irrational $\theta$, we then show that the resulting denominators cannot remain bounded, so a subsequence has denominators tending to infinity. Dividing the finite estimate by $q$ gives the rational approximation estimate, and irrationality rules out equality in the borderline case.
[/proofplan]
[step:Place the first $N+1$ fractional parts into $N$ equal intervals]
For each real number $x \in \mathbb{R}$, let $\lfloor x \rfloor \in \mathbb{Z}$ denote the greatest integer satisfying $\lfloor x \rfloor \leq x$, and define the fractional part map $\{\cdot\}: \mathbb{R} \to [0,1)$ by
\begin{align*}
\{x\} = x - \lfloor x \rfloor.
\end{align*}
For each integer $j \in \{0,1,\dots,N-1\}$, define the half-open interval
\begin{align*}
I_j := \left[\frac{j}{N},\frac{j+1}{N}\right) \subset [0,1).
\end{align*}
These $N$ intervals are pairwise disjoint and their union is $[0,1)$.
Now consider the $N+1$ [real numbers](/page/Real%20Numbers)
\begin{align*}
\{0\theta\},\{1\theta\},\dots,\{N\theta\} \in [0,1).
\end{align*}
Since $N+1$ objects are assigned to the $N$ intervals $I_0,\dots,I_{N-1}$, there exist integers $r,s \in \{0,1,\dots,N\}$ with $r < s$ and an index $j \in \{0,1,\dots,N-1\}$ such that
\begin{align*}
\{r\theta\},\{s\theta\} \in I_j.
\end{align*}
Because $I_j$ has length $1/N$, this gives
\begin{align*}
|\{s\theta\}-\{r\theta\}| < \frac{1}{N}.
\end{align*}
[guided]
The purpose of fractional parts is to ignore integer shifts of multiples of $\theta$. Define the fractional part map $\{\cdot\}: \mathbb{R} \to [0,1)$ by
\begin{align*}
\{x\} = x - \lfloor x \rfloor,
\end{align*}
where $\lfloor x \rfloor$ is the greatest integer not exceeding $x$. Thus each multiple $k\theta$ is decomposed as an integer part plus a fractional part:
\begin{align*}
k\theta = \lfloor k\theta \rfloor + \{k\theta\}.
\end{align*}
We divide the interval $[0,1)$ into the $N$ half-open intervals
\begin{align*}
I_j := \left[\frac{j}{N},\frac{j+1}{N}\right), \qquad j \in \{0,1,\dots,N-1\}.
\end{align*}
The half-open convention ensures that every point of $[0,1)$ lies in exactly one interval, including points that land on subdivision boundaries.
Now we place the $N+1$ fractional parts
\begin{align*}
\{0\theta\},\{1\theta\},\dots,\{N\theta\}
\end{align*}
into these $N$ intervals. Since there are more fractional parts than intervals, two of them must lie in the same interval. Hence there exist integers $r,s \in \{0,1,\dots,N\}$ with $r < s$ and an index $j \in \{0,1,\dots,N-1\}$ such that
\begin{align*}
\{r\theta\},\{s\theta\} \in I_j.
\end{align*}
Because the interval $I_j$ has length $1/N$, the distance between any two points in it is strictly less than $1/N$. Therefore
\begin{align*}
|\{s\theta\}-\{r\theta\}| < \frac{1}{N}.
\end{align*}
This is the key approximation step: two multiples of $\theta$ have fractional parts very close to each other, so their difference is very close to an integer.
[/guided]
[/step]
[step:Subtract the corresponding multiples to obtain the denominator bound]
Define
\begin{align*}
q := s-r \in \mathbb{N}.
\end{align*}
Since $0 \leq r < s \leq N$, we have
\begin{align*}
1 \leq q \leq N.
\end{align*}
Define the integer
\begin{align*}
p := \lfloor s\theta \rfloor - \lfloor r\theta \rfloor \in \mathbb{Z}.
\end{align*}
Using the identity $k\theta = \lfloor k\theta \rfloor + \{k\theta\}$ for $k \in \{r,s\}$, we compute first from the definitions of $p$ and $q$ that
\begin{align*}
q\theta - p = (s-r)\theta - \bigl(\lfloor s\theta \rfloor - \lfloor r\theta \rfloor\bigr).
\end{align*}
Rearranging the four terms gives
\begin{align*}
q\theta - p = \bigl(s\theta - \lfloor s\theta \rfloor\bigr) - \bigl(r\theta - \lfloor r\theta \rfloor\bigr).
\end{align*}
Using the definition of fractional part on the two parenthesized terms, we obtain
\begin{align*}
q\theta - p = \{s\theta\} - \{r\theta\}.
\end{align*}
Taking absolute values and using the preceding estimate gives
\begin{align*}
|q\theta-p| = |\{s\theta\}-\{r\theta\}| < \frac{1}{N} \leq \frac{1}{N}.
\end{align*}
This proves the first assertion.
[/step]
[step:Show that irrationality forces unbounded denominators]
Assume now that $\theta$ is irrational. For each $N \in \mathbb{N}$, choose integers $p_N \in \mathbb{Z}$ and $q_N \in \mathbb{N}$ with $1 \leq q_N \leq N$ and
\begin{align*}
|q_N\theta - p_N| \leq \frac{1}{N}.
\end{align*}
We prove that the set $\{q_N : N \in \mathbb{N}\}$ is unbounded.
Suppose instead that there exists $Q \in \mathbb{N}$ such that $q_N \leq Q$ for every $N \in \mathbb{N}$. For each $q \in \{1,\dots,Q\}$, the number $q\theta$ is irrational, so
\begin{align*}
\delta_q := \operatorname{dist}(q\theta,\mathbb{Z}) := \inf_{m \in \mathbb{Z}} |q\theta-m|
\end{align*}
is positive. Since the finite set $\{\delta_1,\dots,\delta_Q\}$ consists of positive real numbers, define
\begin{align*}
\delta := \min_{1 \leq q \leq Q} \delta_q > 0.
\end{align*}
For every $N \in \mathbb{N}$, the integer $p_N$ and the bound $q_N \leq Q$ imply
\begin{align*}
|q_N\theta-p_N| \geq \delta.
\end{align*}
But choosing $N > 1/\delta$ gives
\begin{align*}
|q_N\theta-p_N| \leq \frac{1}{N} < \delta,
\end{align*}
a contradiction. Hence the denominators $q_N$ are unbounded.
[/step]
[step:Pass to infinitely many strict rational approximations]
Since the sequence $(q_N)_{N \in \mathbb{N}}$ is unbounded, choose an increasing sequence of positive integers $(N_k)_{k \in \mathbb{N}}$ such that
\begin{align*}
q_{N_k} \to \infty
\end{align*}
as $k \to \infty$. For each $k \in \mathbb{N}$, divide the inequality
\begin{align*}
|q_{N_k}\theta-p_{N_k}| \leq \frac{1}{N_k}
\end{align*}
by $q_{N_k} > 0$ to obtain
\begin{align*}
\left|\theta-\frac{p_{N_k}}{q_{N_k}}\right|
\leq \frac{1}{q_{N_k}N_k}.
\end{align*}
Because $q_{N_k} \leq N_k$, we have
\begin{align*}
\frac{1}{q_{N_k}N_k} \leq \frac{1}{q_{N_k}^2}.
\end{align*}
Thus
\begin{align*}
\left|\theta-\frac{p_{N_k}}{q_{N_k}}\right|
\leq \frac{1}{q_{N_k}^2}.
\end{align*}
We now show that the inequality is strict. If equality held for some $k$, then both inequalities above would be equalities. Therefore $N_k=q_{N_k}$ and
\begin{align*}
|q_{N_k}\theta-p_{N_k}|=\frac{1}{q_{N_k}}.
\end{align*}
Hence
\begin{align*}
q_{N_k}\theta-p_{N_k}=\frac{1}{q_{N_k}}
\qquad \text{or} \qquad
q_{N_k}\theta-p_{N_k}=-\frac{1}{q_{N_k}}.
\end{align*}
Solving for $\theta$ gives
\begin{align*}
\theta = \frac{p_{N_k}q_{N_k}+1}{q_{N_k}^2}
\qquad \text{or} \qquad
\theta = \frac{p_{N_k}q_{N_k}-1}{q_{N_k}^2},
\end{align*}
which is rational, contradicting the irrationality of $\theta$. Therefore, for every $k \in \mathbb{N}$,
\begin{align*}
\left|\theta-\frac{p_{N_k}}{q_{N_k}}\right| < \frac{1}{q_{N_k}^2}.
\end{align*}
Finally, these rational numbers are infinitely many distinct values. If only finitely many distinct rationals occurred among $p_{N_k}/q_{N_k}$, then the positive distances from $\theta$ to those finitely many rationals would have a positive minimum, since $\theta$ is irrational and hence is not equal to any of them. But the estimate
\begin{align*}
\left|\theta-\frac{p_{N_k}}{q_{N_k}}\right| < \frac{1}{q_{N_k}^2}
\end{align*}
tends to $0$ because $q_{N_k} \to \infty$, contradicting that positive minimum. Hence there are infinitely many distinct rational numbers $p/q$ satisfying
\begin{align*}
\left|\theta-\frac{p}{q}\right| < \frac{1}{q^2}.
\end{align*}
[/step]
