Let
\[\frac{p_n}{q_n}\]
be the nth convergent of the infinite continued fraction representing the irrational number \[x\]
, and let \[\frac{a}{b}\]
be any rational number with \[0 \lt b \lt q_{n+1}\]
, Then for \[n \gt 1\]
, \[\| q_n x - p_n \| \le \| nx-a \|\]
with equality holding only of \[a=p_n, \; b=q_n\]
.Proof
Let
\[\frac{a}{b}\]
be a rational number with \[b \lt q_{n+1}\]
and suppose it is not the case that \[a=p_n, \; b=q_n\]
, for which the inequality holds.Consider the system
\[a=rp_n+sp_{n+1}\]
(1)\[b=rq_n+sq_{n+1}\]
(2)\[q_n \times (1)-p_n \times (2)\]
gives\[aq_n-bp_n=s(sp_{n+1}q_n-p_nq_{n+1})\]
and using Properties of Convergents of Finite Continued Fractions we write \[s=(-1)^{n+1} (aq_n-bp_n)\]
.Similarly
\[r=(-1)^{n+1}(bp_{n+1}-aq_{n+1})\]
&.\[r, \; s \in \mathbb{N}\]
and neither is zero (if \[r=0\]
then \[aq_{n+1}=bp_{n+1}\]
and Euclid's Lemma forces \[q_{n+1}\]
to divide \[b\]
since \[gcd(p_{n+1}, \; q_{n+1})=1\]
and this contradicts \[0 \lt b \lt q_{n+1}\]
. If \[s=0\]
then \[\frac{a}{b} = \frac{p_n}{q_n}\]
which has been excluded).\[0 \lt b \lt rq_n+sq_{n+1} \lt q_{n+1}\]
so the non zero integers \[r, \; s\]
must have opposite sign.\[x- \frac{p_n}{q_n}, \; x- \frac{p_{n+1}}{q_{n+1}}\]
also have opposite signs because the convergents \[\frac{p_n}{q_n}, \; \frac{p_{n+1}}{q_{n+1}}\]
are alternately less than and greater than \[x\]
. It follows that \[r(q_nx-p_n)\]
and \[s(q_{n+1}x-p_{n+1})\]
have the same sign.\[\begin{equation} \begin{aligned} \| bx-a \| &= \| (rq_n-sq_{n+1})x -(rp_n+sp_{n+1} ) \| \\ &= \| r(q_nx-p_n ) +s(q_{n+1} x-p_{n+1}) \| \\ &= \| r \| \| q_nx-p_n \| + \| s \| \| q_{n+1} x -p_{n+1} \| \\ & \gt \| r \| \| q_nx-p_n \| \ge \| s \| \| q_n x -p_n \| \end{aligned} \end{equation}\]