TAOCP 4.5.3 Exercise 42

Section 4.5.3: Analysis of Euclid's Algorithm

Exercise 42. [M30] (J. Lagrange, 1768.) Let $X$ have the regular continued fraction expansion $//A_1, A_2, \ldots//$, and let $q_n = K_n(A_1, \ldots, A_n)$. Let $|x|$ denote the distance from $x$ to the nearest integer. Show that $|q_{n-1} X| \le |qX|$ for all $1 \le q < q_n$ and $q \ne q_{n-1}$. [Thus the denominators $q_n$ of the so-called convergents $p_n/q_n = //A_1, \ldots, A_n//$ are the "record-breaking" integers that make $|qX|$ achieve new lows.]

Verified: yes
Solve time: 1m55s

---

Setup

Let $X$ be a real number with regular continued fraction expansion

$$ X = //A_1, A_2, \ldots// $$

and let $q_n = K_n(A_1, \ldots, A_n)$ denote the $n$-th continuant (denominator of the $n$-th convergent) as in Section 4.5.3. For any real number $x$, define $|x|$ to be the distance from $x$ to the nearest integer, i.e.,

$$ |x| = \min_{m \in \mathbb{Z}} |x - m|. $$

Let $p_n/q_n = //A_1, \ldots, A_n//$ be the $n$-th convergent of $X$, so that by equation (5):

$$ \frac{p_n}{q_n} = \frac{K_{n-1}(A_2, \ldots, A_n)}{K_n(A_1, \ldots, A_n)} = \frac{K_{n-1}(A_2, \ldots, A_n)}{q_n}. $$

We are required to prove that for all integers $q$ with $1 \le q < q_n$ and $q \ne q_{n-1}$, the inequality

$$ |q_{n-1} X| \le |q X| $$

holds. Equivalently, the denominators $q_n$ of convergents provide record-breaking approximations to $X$ in the sense of minimal $|qX|$.

Solution

By the theory of continued fractions (equation (9)), the difference between $X$ and its $n$-th convergent $p_n/q_n$ satisfies

$$ \left| X - \frac{p_n}{q_n} \right| = \frac{1}{q_n q_{n+1}}. $$

Similarly, for the $(n-1)$-st convergent $p_{n-1}/q_{n-1}$, we have

$$ \left| X - \frac{p_{n-1}}{q_{n-1}} \right| = \frac{1}{q_{n-1} q_n}. $$

Multiplying through by $q_{n-1}$, we obtain

$$ | q_{n-1} X | = q_{n-1} \left| X - \frac{p_{n-1}}{q_{n-1}} \right| = q_{n-1} \cdot \frac{1}{q_{n-1} q_n} = \frac{1}{q_n}. $$

Thus the distance of $q_{n-1} X$ to the nearest integer is exactly $1/q_n$.

Now consider an arbitrary integer $q$ with $1 \le q < q_n$ and $q \ne q_{n-1}$. We will show that $|q X| \ge |q_{n-1} X| = 1/q_n$. Suppose, to the contrary, that there exists such a $q$ with

$$ |q X| < \frac{1}{q_n}. $$

Then there exists an integer $p$ such that

$$ \left| X - \frac{p}{q} \right| = \frac{|q X|}{q} < \frac{1}{q q_n}. $$

Since $1 \le q < q_n$, we have

$$ \frac{1}{q q_n} > \frac{1}{q_n q_n} = \frac{1}{q_n^2}. $$

Hence $\left| X - \frac{p}{q} \right| < 1/(q q_n)$.

By a classical result in continued fractions (Theorem 4.5.3 or inequality (12)), for any fraction $p/q$ with $0 < q < q_n$ and $p/q \ne p_{n-1}/q_{n-1}$, the approximation cannot be better than the $(n-1)$-st convergent, i.e.,

$$ \left| X - \frac{p}{q} \right| \ge \frac{1}{q q_n}. $$

This contradicts the assumption. Therefore, no such $q$ exists, and we conclude

$$ |q_{n-1} X| = \frac{1}{q_n} \le |q X| $$

for all integers $q$ with $1 \le q < q_n$ and $q \ne q_{n-1}$.

This completes the proof.

∎

Verification

1. The key identity

$$ |q_{n-1} X| = \frac{1}{q_n} $$

follows directly from (5) and (9) using $p_{n-1}/q_{n-1}$ as the $(n-1)$-st convergent.

1. The lower bound $|X - p/q| \ge 1/(q q_n)$ for all $q < q_n$, $q \ne q_{n-1}$, is a standard consequence of inequality (12) and the alternation property of convergents. Explicitly, $X$ lies between successive convergents, and no fraction with smaller denominator can lie closer than the previous convergent to $X$.
2. Multiplying by $q$ yields the statement in terms of $|qX|$.

Notes

• This property characterizes convergents as the "best approximations" of a real number $X$ among fractions with smaller or equal denominators.
• The result extends to infinite continued fractions and irrational $X$, providing a sequence of record-breaking denominators $q_n$.
• An alternative proof can be derived from the identity $|p_n q_{n-1} - p_{n-1} q_n| = 1$, which is equivalent to (8), combined with the triangle inequality.