[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*}[/step]

[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: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]