I'm looking for a proof of the following result (theorem 6.14 of the book Cryptography. Theory and practice by Paterson and Stinson):
Theorem 6.14 Suppose that $\text{gcd}(a,b) = \text{gcd}(c,d) = 1$ and: $$\Bigl\rvert \frac{a}{b} – \frac{c}{d}\Bigr\rvert < \frac{1}{2d^2}$$ Then $c/d$ is one of the convergents of the continued fraction expansion of $a/b$.
I already know the analogous result for irrational numbers (theorem 7.14 of the book An Introduction to the Theory of Numbers by Niven, Zuckerman and Montgomery with a slight change of notations to avoid ambiguities):
Theorem 7.14 Let $\xi$ denote any irrational number. If there is a rational number $c/d$ with $d \geq 1$ such that: $$\Bigl\rvert \xi – \frac{c}{d} \Bigr\rvert < \frac{1}{2d^2}$$ Then $c/d$ equals one of the convergents of the continued fraction expansion of $\xi$.
However, it seems to me that the proof of theorem 7.14 cannot immediately be generalized to the case of rational numbers: one calls $h_j/k_j$ the $j$-th convergent of the simple continued fraction expansion of $\xi$ and then one uses the fact that $\lim k_j = +\infty$ to pick an integer $n$ such that $k_n \leq b < k_{n+1}$. This cannot be done in the case of rational numbers (theorem 6.14) simply because the convergents of the continued fraction expansion of $a/b$ are finite: it might be the case that the convergents of $a/b$ are $h_0/k_0,h_1/k_1,\dots,h_m/k_m = a/b$ and that $b \leq d$. So, how exactly is theorem 6.14 established?
Best Answer
As you noted, the claim also holds for irrational numbers. I will give a proof that works for all real numbers, i.e. I will prove:
Let $x\in\mathbb R$ and $c,d\in\mathbb Z$ coprime such that $$\left|x-\frac cd\right|<\frac1{2d^2}.$$ Then $\frac cd$ is a convergent of the continued fraction expansion of $x$.
Proof: If $x=\frac cd$, the claim is obvious. Otherwise write $$x-\frac cd=\varepsilon\cdot\frac{\theta}{d^2},\qquad \varepsilon=\pm1,\ 0<\theta<\frac12.$$ Let $\frac cd=[a_0;a_1,\ldots,a_n]$ be the (finite) continued fraction expansion of $\frac cd$. Since one can vary the length of such an expansion by $1$, wlog assume $(-1)^n=\varepsilon$. Write $\frac{u_k}{v_k}=[a_0;a_1,\ldots,a_k]$ for the $k$-th convergent of $\frac cd$, with $u_k,v_k$ coprime. Then let \begin{align}\xi:=\frac{v_{n-1}x-u_{n-1}}{-dx+c}\quad\Longrightarrow\quad x=\frac{c\xi+u_{n-1}}{d\xi+v_{n-1}}.\tag{$\ast$}\end{align}
A short calculation, using the well-known formula $u_kv_{k-1}-u_{k-1}v_k=(-1)^{k+1}$, now gives $$\varepsilon\cdot\frac{\theta}{d^2}=x-\frac cd=\frac{\varepsilon}{d(d\xi+v_{n-1})} \quad\Longrightarrow \quad\frac1\theta=\xi+\frac{v_{n-1}}d.$$ Now since $\frac1\theta>2$ and $\frac{v_{n-1}}d=\frac{v_{n-1}}{v_n}<1$ (denominators of convergents are increasing), we conclude that $\xi>1$. Equation ($\ast$) implies that $x=[a_0;a_1,\ldots,a_n,\xi]$ and since $\xi>1$ we can indeed conclude that the continued fraction expansion of $x$ starts with $[a_0;a_1,\ldots,a_n,\ldots]$.
Edit (sketch of proofs of basic formulas, as requested): Let $x=[a_0;a_1,\ldots,a_n,\xi]$ with $a_0\in\mathbb Z$, $a_i\in\mathbb N$, $\xi\in\mathbb R$. Then one easily proves by induction that $x=\frac uv$ with $u$ and $v$ given by $$\binom uv=A_0\cdots A_n\binom\xi1,\qquad A_k:=\begin{pmatrix}a_k&1\\1&0\end{pmatrix}.$$ Now let $x=[a_0;a_1,\ldots]$ be a continued fraction expansion, and denote the convergents as $\frac{u_k}{v_k}$. Then by the equation above one infers that $$\begin{pmatrix}u_n&u_{n-1}\\v_n&v_{n-1}\end{pmatrix}=A_0\cdots A_n.$$ Taking determinants now gives the "well-known formula" cited in the proof. Combining these two equations gives $$\binom uv=\begin{pmatrix}u_n&u_{n-1}\\v_n&v_{n-1}\end{pmatrix}\binom\xi1\Longleftrightarrow x=\frac{u_n\xi+u_{n-1}}{v_n\xi+v_{n-1}},$$ which is $(\ast)$. Combining this with the first statement of the edit, we get that ($\ast$) holds if and only if $x=[a_0;a_1,\ldots,a_n,\xi]$. (The only if part follows since $\xi$ is uniquely determined by these formulas.)