[proofplan] We compare the reduced rational $p/q$ with the last continued fraction convergent whose denominator does not exceed $q$. If $p/q$ is not that convergent, the best-approximation property of continued fraction convergents gives a strictly better approximation to $\theta$ after multiplying by denominators. The assumed Legendre bound then forces the two distinct reduced rationals $p/q$ and $p_n/q_n$ to be closer than the elementary lower bound $1/(qq_n)$ for distinct reduced rationals, giving a contradiction. [/proofplan] [step:Choose the relevant convergent denominator] Let \begin{align*} \theta = [a_0; a_1, a_2, \dots] \end{align*} be the continued fraction expansion of $\theta$, and let \begin{align*} \frac{p_k}{q_k} \end{align*} denote its $k$th convergent, with $p_k \in \mathbb{Z}$, $q_k \in \mathbb{N}$, and $\gcd(p_k,q_k)=1$. Choose an index $n$ such that \begin{align*} q_n \le q < q_{n+1}. \end{align*} In the exceptional case where $q_0=q_1=1$ and $q=1$, choose $n=1$. If $\frac{p}{q}=\frac{p_n}{q_n}$, then $\frac{p}{q}$ is a convergent and there is nothing to prove. Hence assume, for contradiction, that \begin{align*} \frac{p}{q} \ne \frac{p_n}{q_n}. \end{align*} [/step] [step:Use the best approximation property of convergents] By the [Best Approximation Property of Continued Fraction Convergents](/theorems/???), since $0<q<q_{n+1}$ and $\frac{p}{q}\ne \frac{p_n}{q_n}$, we have \begin{align*} |q_n\theta - p_n| < |q\theta - p|. \end{align*} The hypothesis gives \begin{align*} |q\theta-p| = q\left|\theta-\frac{p}{q}\right| < q \cdot \frac{1}{2q^2} = \frac{1}{2q}. \end{align*} Therefore \begin{align*} \left|\theta-\frac{p_n}{q_n}\right| = \frac{|q_n\theta-p_n|}{q_n} < \frac{|q\theta-p|}{q_n} < \frac{1}{2qq_n}. \end{align*} [guided] The point of choosing $n$ with $q_n \le q < q_{n+1}$ is that the $n$th convergent is the best approximation among all rationals whose denominator is smaller than $q_{n+1}$. Since our rational $\frac{p}{q}$ has denominator $q<q_{n+1}$ and is assumed not to equal $\frac{p_n}{q_n}$, the [Best Approximation Property of Continued Fraction Convergents](/theorems/???) gives \begin{align*} |q_n\theta - p_n| < |q\theta - p|. \end{align*} Now we translate the assumed estimate for $\frac{p}{q}$ into the same denominator-weighted form: \begin{align*} |q\theta-p| = q\left|\theta-\frac{p}{q}\right| < q \cdot \frac{1}{2q^2} = \frac{1}{2q}. \end{align*} Dividing the strict inequality $|q_n\theta-p_n|<|q\theta-p|$ by the positive integer $q_n$ gives \begin{align*} \left|\theta-\frac{p_n}{q_n}\right| = \frac{|q_n\theta-p_n|}{q_n} < \frac{|q\theta-p|}{q_n} < \frac{1}{2qq_n}. \end{align*} Thus the convergent $\frac{p_n}{q_n}$ is not merely a good approximation; under the contradiction assumption it is close enough to $\theta$ to force an impossible closeness to $\frac{p}{q}$. [/guided] [/step] [step:Force two distinct reduced rationals to be too close] Using the triangle inequality with the two estimates above, we obtain \begin{align*} \left|\frac{p}{q}-\frac{p_n}{q_n}\right| \le \left|\theta-\frac{p}{q}\right| + \left|\theta-\frac{p_n}{q_n}\right|. \end{align*} Substituting the Legendre hypothesis and the estimate from the previous step gives \begin{align*} \left|\frac{p}{q}-\frac{p_n}{q_n}\right| < \frac{1}{2q^2} + \frac{1}{2qq_n}. \end{align*} Since $q_n \le q$, we have $1/q^2 \le 1/(qq_n)$, and therefore \begin{align*} \frac{1}{2q^2} + \frac{1}{2qq_n} \le \frac{1}{qq_n}. \end{align*} Hence \begin{align*} \left|\frac{p}{q}-\frac{p_n}{q_n}\right| < \frac{1}{qq_n}. \end{align*} [guided] We now turn two separate approximations to $\theta$ into an estimate on the distance between the two rational numbers themselves. The triangle inequality on $\mathbb{R}$ gives \begin{align*} \left|\frac{p}{q}-\frac{p_n}{q_n}\right| \le \left|\theta-\frac{p}{q}\right| + \left|\theta-\frac{p_n}{q_n}\right|. \end{align*} The first term is controlled by the hypothesis of the theorem: \begin{align*} \left|\theta-\frac{p}{q}\right| < \frac{1}{2q^2}. \end{align*} The second term is controlled by the estimate proved in the previous step: \begin{align*} \left|\theta-\frac{p_n}{q_n}\right| < \frac{1}{2qq_n}. \end{align*} Substituting these two strict inequalities into the triangle inequality gives \begin{align*} \left|\frac{p}{q}-\frac{p_n}{q_n}\right| < \frac{1}{2q^2} + \frac{1}{2qq_n}. \end{align*} The choice of $n$ gives $q_n \le q$. Since $q$ and $q_n$ are positive integers, this implies $qq_n \le q^2$, hence $1/q^2 \le 1/(qq_n)$. Therefore \begin{align*} \frac{1}{2q^2} + \frac{1}{2qq_n} \le \frac{1}{2qq_n} + \frac{1}{2qq_n} = \frac{1}{qq_n}. \end{align*} Combining the last two displayed inequalities yields \begin{align*} \left|\frac{p}{q}-\frac{p_n}{q_n}\right| < \frac{1}{qq_n}. \end{align*} This is the decisive upper bound: two distinct reduced rationals with denominators $q$ and $q_n$ cannot be this close. [/guided] [/step] [step:Contradict the separation of reduced rationals] Because both fractions are reduced and are distinct, the integer \begin{align*} pq_n-p_nq \end{align*} is nonzero. Hence $|pq_n-p_nq|\ge 1$, and \begin{align*} \left|\frac{p}{q}-\frac{p_n}{q_n}\right| = \frac{|pq_n-p_nq|}{qq_n} \ge \frac{1}{qq_n}. \end{align*} This contradicts the strict inequality obtained in the previous step. Therefore the assumption $\frac{p}{q}\ne \frac{p_n}{q_n}$ is false, so \begin{align*} \frac{p}{q}=\frac{p_n}{q_n}. \end{align*} Thus $\frac{p}{q}$ is a convergent of the continued fraction expansion of $\theta$. [guided] We finish by using the elementary separation of distinct reduced rationals. The fraction $p/q$ is reduced by hypothesis, and the convergent $p_n/q_n$ is reduced by the standard construction of continued fraction convergents. Under the contradiction assumption, these two reduced fractions are distinct, so the integer \begin{align*} pq_n-p_nq \end{align*} is nonzero. Every nonzero integer has absolute value at least $1$, hence \begin{align*} |pq_n-p_nq| \ge 1. \end{align*} Computing the distance between the two rationals gives \begin{align*} \left|\frac{p}{q}-\frac{p_n}{q_n}\right| = \frac{|pq_n-p_nq|}{qq_n} \ge \frac{1}{qq_n}. \end{align*} This lower bound contradicts the strict upper bound \begin{align*} \left|\frac{p}{q}-\frac{p_n}{q_n}\right| < \frac{1}{qq_n} \end{align*} obtained in the preceding step. Therefore the contradiction assumption $\frac{p}{q}\ne \frac{p_n}{q_n}$ is false, and so \begin{align*} \frac{p}{q}=\frac{p_n}{q_n}. \end{align*} Since $p_n/q_n$ is, by definition, the $n$th convergent of the continued fraction expansion of $\theta$, the rational $p/q$ is a convergent of that expansion. [/guided] [/step]