[proofplan] We factor the residue $p_n^2 - N q_n^2$ as a difference of squares, isolating $\sqrt{N} - p_n/q_n$ (controlled by the standard convergent bound $1/(q_n q_{n+1})$) and $\sqrt{N} + p_n/q_n$ (bounded by $2\sqrt{N} + 1/(q_n q_{n+1})$ via the same bound applied in the other direction). Multiplying the two bounds and using $q_{n+1} > q_n \geq 1$ contracts the resulting expression to $2\sqrt{N}$. [/proofplan] [step:Set up hypotheses and factor the residue as a difference of squares] Let $N$ be a positive integer that is not a perfect square, so that $\sqrt{N} \in \mathbb{R} \setminus \mathbb{Q}$, and let $[a_0, a_1, a_2, \ldots]$ be its simple continued fraction expansion with convergents $p_n/q_n$ for $n \geq 0$. We use throughout that $q_n \in \mathbb{Z}_{\geq 1}$ and the denominators are strictly increasing, $q_{n+1} > q_n$ for $n \geq 1$ (and $q_1 \geq 1 = q_0$ in the standard normalisation, so $q_{n+1} \geq q_n$ for all $n \geq 0$, with strict inequality for $n \geq 1$). Factoring as a difference of squares, \begin{align*} p_n^2 - N q_n^2 = q_n^2 \left( \frac{p_n^2}{q_n^2} - N \right) = q_n^2 \left( \frac{p_n}{q_n} - \sqrt{N} \right) \left( \frac{p_n}{q_n} + \sqrt{N} \right). \end{align*} Taking absolute values, \begin{align*} |p_n^2 - N q_n^2| = q_n^2 \left| \sqrt{N} - \frac{p_n}{q_n} \right| \cdot \left| \sqrt{N} + \frac{p_n}{q_n} \right|. \end{align*} [/step] [step:Apply the standard convergent error bound for continued fractions] By the [convergent error bound](/theorems/1760), for the irrational $\theta = \sqrt{N}$ and every $n \geq 0$, \begin{align*} \left| \sqrt{N} - \frac{p_n}{q_n} \right| < \frac{1}{q_n q_{n+1}}. \end{align*} The hypotheses of that theorem are verified: $\sqrt{N} \in \mathbb{R} \setminus \mathbb{Q}$ since $N$ is not a perfect square, and $p_n/q_n$ are the convergents of its continued fraction expansion with $q_n \geq 1$ and $q_{n+1} > q_n \geq 1$ for $n \geq 1$. [guided] We invoke the sharp error bound for continued fraction convergents: for any irrational $\theta$ with convergents $p_n/q_n$, \begin{align*} \left| \theta - \frac{p_n}{q_n} \right| < \frac{1}{q_n q_{n+1}} \quad \text{for every } n \geq 0. \end{align*} This theorem requires $\theta \in \mathbb{R} \setminus \mathbb{Q}$. We verify this hypothesis: by assumption $N$ is a positive integer that is not a perfect square, and a standard argument shows $\sqrt{N}$ is then irrational (if $\sqrt{N} = p/q$ in lowest terms with $q \geq 1$, then $N q^2 = p^2$ forces $q \mid p$ hence $q = 1$, so $N = p^2$ is a perfect square, contradiction). Applying the bound with $\theta = \sqrt{N}$ gives the desired inequality for every $n \geq 0$. [/guided] [/step] [step:Bound $|\sqrt{N} + p_n/q_n|$ by the triangle inequality] We bound the second factor $|\sqrt{N} + p_n/q_n|$ using the triangle inequality: \begin{align*} \left| \sqrt{N} + \frac{p_n}{q_n} \right| = \left| 2\sqrt{N} + \left( \frac{p_n}{q_n} - \sqrt{N} \right) \right| \leq 2\sqrt{N} + \left| \frac{p_n}{q_n} - \sqrt{N} \right| < 2\sqrt{N} + \frac{1}{q_n q_{n+1}}, \end{align*} where the final strict inequality uses the convergent bound from the previous step and $\sqrt{N} > 0$. [guided] We want to bound the second factor in the factorisation, $|\sqrt{N} + p_n/q_n|$. The natural strategy is to compare it with $2\sqrt{N}$, since $p_n/q_n \approx \sqrt{N}$. Write \begin{align*} \sqrt{N} + \frac{p_n}{q_n} = 2\sqrt{N} + \left( \frac{p_n}{q_n} - \sqrt{N} \right), \end{align*} so by the triangle inequality $|a + b| \leq |a| + |b|$ (valid for all real numbers), \begin{align*} \left| \sqrt{N} + \frac{p_n}{q_n} \right| \leq |2\sqrt{N}| + \left| \frac{p_n}{q_n} - \sqrt{N} \right| = 2\sqrt{N} + \left| \sqrt{N} - \frac{p_n}{q_n} \right|, \end{align*} using $N > 0$ (so $2\sqrt{N} > 0$). Substituting the convergent bound from the previous step, \begin{align*} \left| \sqrt{N} + \frac{p_n}{q_n} \right| < 2\sqrt{N} + \frac{1}{q_n q_{n+1}}. \end{align*} Note the strict inequality is preserved: the convergent bound is strict, so its addition to $2\sqrt{N}$ gives a strict bound. [/guided] [/step] [step:Multiply the two bounds and simplify] Combining the factorisation from the first step with the two bounds, \begin{align*} |p_n^2 - N q_n^2| &= q_n^2 \left| \sqrt{N} - \frac{p_n}{q_n} \right| \cdot \left| \sqrt{N} + \frac{p_n}{q_n} \right| \\ &< q_n^2 \cdot \frac{1}{q_n q_{n+1}} \cdot \left( 2\sqrt{N} + \frac{1}{q_n q_{n+1}} \right) \\ &= \frac{q_n}{q_{n+1}} \cdot \left( 2\sqrt{N} + \frac{1}{q_n q_{n+1}} \right) \\ &= \frac{2 q_n \sqrt{N}}{q_{n+1}} + \frac{1}{q_{n+1}^2}. \end{align*} [/step] [step:Bound each term using $q_{n+1} \geq q_n \geq 1$] The denominator sequence satisfies $q_{n+1} \geq q_n$ for all $n \geq 0$ (strictly for $n \geq 1$, with equality only possible at $n = 0$ when $q_0 = q_1 = 1$). In every case $q_{n+1} \geq 1$ and $q_n / q_{n+1} \leq 1$. Therefore \begin{align*} \frac{2 q_n \sqrt{N}}{q_{n+1}} \leq 2\sqrt{N}, \qquad \frac{1}{q_{n+1}^2} \leq 1. \end{align*} Adding, \begin{align*} |p_n^2 - N q_n^2| < 2\sqrt{N} + \frac{1}{q_{n+1}^2} - \left( 2\sqrt{N} - \frac{2 q_n \sqrt{N}}{q_{n+1}} \right). \end{align*} This bookkeeping is clumsy; we argue more carefully. Since $q_{n+1} > q_n$ for $n \geq 1$, we have $q_n / q_{n+1} < 1$, which together with $1/q_{n+1}^2 \leq 1/q_{n+1}$ will let us bundle both terms under $2\sqrt{N}$. Explicitly, writing \begin{align*} \frac{2 q_n \sqrt{N}}{q_{n+1}} + \frac{1}{q_{n+1}^2} = \frac{1}{q_{n+1}} \left( 2 q_n \sqrt{N} + \frac{1}{q_{n+1}} \right), \end{align*} and using $1/q_{n+1} \leq 1/q_n$ together with $1/(q_n q_{n+1}) \leq 1$, a direct comparison yields $|p_n^2 - N q_n^2| \leq 2\sqrt{N}$ as proved in the next step. [guided] Before closing, it is worth pausing to see why the bound $2\sqrt{N}$ should emerge. The dominant term in our estimate is $2 q_n \sqrt{N} / q_{n+1}$, which is at most $2\sqrt{N}$ since $q_n / q_{n+1} \leq 1$. The additional $1/q_{n+1}^2$ term is a small correction. The challenge is that the two contributions together must still not exceed $2\sqrt{N}$ — we cannot afford an additive slack. The mechanism that makes this work is the strict inequality from the convergent bound. The strict bound $|\sqrt{N} - p_n/q_n| < 1/(q_n q_{n+1})$ has room to absorb the small $1/q_{n+1}^2$ correction. We make this explicit in the next step by a direct manipulation. [/guided] [/step] [step:Conclude the sharp bound $|p_n^2 - N q_n^2| \leq 2\sqrt{N}$] We start from the strict inequality of the previous estimate and simplify directly. From the factorisation and the two bounds, \begin{align*} |p_n^2 - N q_n^2| &< \frac{q_n^2}{q_n q_{n+1}} \left( 2\sqrt{N} + \frac{1}{q_n q_{n+1}} \right) \\ &= \frac{1}{q_{n+1}} \left( 2 q_n \sqrt{N} + \frac{1}{q_{n+1}} \right). \end{align*} Since $q_{n+1} \geq q_n$ (hence $q_n / q_{n+1} \leq 1$) and $q_{n+1} \geq 1$ (hence $1/q_{n+1}^2 \leq 1/q_{n+1}$), we replace $q_n$ by $q_{n+1}$ in the first term and $1/q_{n+1}$ by $1$ in the second term to obtain the coarser bound \begin{align*} |p_n^2 - N q_n^2| < \frac{1}{q_{n+1}} \left( 2 q_{n+1} \sqrt{N} + 1 \right) = 2\sqrt{N} + \frac{1}{q_{n+1}}. \end{align*} The right-hand side is at most $2\sqrt{N} + 1$ whenever $q_{n+1} \geq 1$, but this is not yet the bound we want. We instead sharpen using a tighter replacement. From the original expression, \begin{align*} \frac{1}{q_{n+1}} \left( 2 q_n \sqrt{N} + \frac{1}{q_{n+1}} \right) = \frac{2 q_n}{q_{n+1}} \sqrt{N} + \frac{1}{q_{n+1}^2}. \end{align*} The coefficient $2 q_n / q_{n+1}$ is strictly less than $2$ whenever $q_{n+1} > q_n$. For $n \geq 1$, this strict inequality holds and the deficit $2 \sqrt{N} - (2 q_n / q_{n+1}) \sqrt{N} = 2(q_{n+1} - q_n)\sqrt{N}/q_{n+1} \geq 2\sqrt{N}/q_{n+1}$ absorbs the remaining term $1/q_{n+1}^2 \leq 1/q_{n+1} \leq 2\sqrt{N}/q_{n+1}$ (using $N \geq 2$, which holds since $N$ is a positive non-square integer so $N \geq 2$). Combining, \begin{align*} \frac{2 q_n}{q_{n+1}} \sqrt{N} + \frac{1}{q_{n+1}^2} \leq 2\sqrt{N}. \end{align*} Therefore $|p_n^2 - N q_n^2| \leq 2\sqrt{N}$, as required. This completes the proof. [guided] We close the argument by tightening the constants. From the previous step, \begin{align*} |p_n^2 - N q_n^2| < \frac{2 q_n}{q_{n+1}} \sqrt{N} + \frac{1}{q_{n+1}^2}. \qquad (\star) \end{align*} We want to show the right-hand side is $\leq 2\sqrt{N}$. Rearranging, this is equivalent to \begin{align*} 2 \sqrt{N} \cdot \frac{q_{n+1} - q_n}{q_{n+1}} \geq \frac{1}{q_{n+1}^2}, \quad \text{i.e.,} \quad 2\sqrt{N} (q_{n+1} - q_n) q_{n+1} \geq 1. \end{align*} We verify this inequality case by case. **Case 1: $n \geq 1$.** Then $q_{n+1} > q_n$, so $q_{n+1} - q_n \geq 1$. Also $q_{n+1} \geq 2$ (since $q_n \geq 1$ and $q_{n+1} > q_n$). Hence \begin{align*} 2\sqrt{N}(q_{n+1} - q_n)q_{n+1} \geq 2\sqrt{N} \cdot 1 \cdot 2 = 4\sqrt{N} \geq 4\sqrt{2} > 1, \end{align*} using $N \geq 2$ (since $N$ is a positive non-square integer, so $N \in \{2, 3, 5, 6, 7, 8, 10, \ldots\}$ and the smallest value is $N = 2$). **Case 2: $n = 0$.** In this case $q_0 = 1$ and $q_1 = a_1 \geq 1$. If $a_1 \geq 1$ strictly, i.e., $q_1 \geq 2$, the argument of Case 1 applies. If $q_1 = 1$, then $q_0 = q_1 = 1$ and the expression $(\star)$ becomes \begin{align*} |p_0^2 - N q_0^2| < 2\sqrt{N} \cdot 1 + 1 = 2\sqrt{N} + 1, \end{align*} which is not the bound we seek. However, $n = 0$ with $q_0 = q_1 = 1$ corresponds to $a_0 = \lfloor \sqrt{N} \rfloor$ and $\theta_1 > 1$ (the first partial quotient is $1$ only when $\sqrt{N} - \lfloor \sqrt{N} \rfloor > 1/2$, else $a_1 \geq 2$). In this edge case we verify the bound directly: $p_0 = a_0$, so \begin{align*} |p_0^2 - N q_0^2| = |a_0^2 - N| = N - a_0^2, \end{align*} since $a_0 = \lfloor \sqrt{N} \rfloor < \sqrt{N}$ gives $a_0^2 < N$. Writing $a_0 = \sqrt{N} - \varepsilon$ with $0 < \varepsilon < 1$, \begin{align*} N - a_0^2 = (\sqrt{N} - a_0)(\sqrt{N} + a_0) = \varepsilon(2\sqrt{N} - \varepsilon) < 2\sqrt{N} \cdot 1 = 2\sqrt{N}. \end{align*} In every case, $|p_n^2 - N q_n^2| \leq 2\sqrt{N}$. This completes the proof. [/guided] [/step]