TAOCP 4.5.3 Exercise 18

Section 4.5.3: Analysis of Euclid's Algorithm

Exercise 18. [M25] Show that $//a_1, a_2, \ldots, a_m, t_1, a_1, a_2, \ldots, a_m, t_2, a_1, a_2, \ldots, a_m, x_3, \ldots// - //a_m, \ldots, a_1, t_1, a_m, \ldots, a_1, t_2, \ldots//$ does not depend on $x_1, x_2, x_3, \ldots$. Hint: Multiply both continued fractions by $K_m(a_1, a_2, \ldots, a_m)$.

Verified: no
Solve time: 10m06s

---

Exercise 4.5.3.18 [M25], Corrected Solution

We are asked to show that

[ //a_1, a_2, \ldots, a_m, t_1, a_1, \ldots, a_m, t_2, a_1, \ldots, a_m, x_3, \ldots//

//a_m, \ldots, a_1, t_1, a_m, \ldots, a_1, t_2, \ldots// ]

is independent of (x_1, x_2, x_3, \ldots). The hint suggests multiplying both continued fractions by (K_m(a_1, \ldots, a_m)). We proceed rigorously using continuants.

Step 1: Represent the continued fractions using continuants

For any finite sequence ((b_1, \ldots, b_n)), the continuant (K_n(b_1, \ldots, b_n)) is defined recursively by

[ K_0 = 1, \quad K_1(b_1) = b_1, \quad K_n(b_1, \ldots, b_n) = b_n K_{n-1}(b_1, \ldots, b_{n-1}) + K_{n-2}(b_1, \ldots, b_{n-2}). ]

A finite continued fraction satisfies

[ //b_1, \ldots, b_n// = \frac{K_n(b_1, \ldots, b_n)}{K_{n-1}(b_2, \ldots, b_n)}. ]

Denote (K_m := K_m(a_1, \ldots, a_m)). Let

[ A := //a_1, \ldots, a_m, t_1, a_1, \ldots, a_m, t_2, a_1, \ldots, a_m, x_3, \ldots//, ]

[ B := //a_m, \ldots, a_1, t_1, a_m, \ldots, a_1, t_2, \ldots//. ]

Step 2: Multiply each continued fraction by (K_m) and expand using the concatenation formula

The concatenation identity for continuants states that, for sequences ((u_1, \ldots, u_r)) and ((v_1, \ldots, v_s)),

[ K_{r+s}(u_1, \ldots, u_r, v_1, \ldots, v_s) = K_r(u_1, \ldots, u_r) K_s(v_1, \ldots, v_s) + K_{r-1}(u_1, \ldots, u_{r-1}) K_{s-1}(v_2, \ldots, v_s). ]

We apply this to the blocks of (a_1, \ldots, a_m) in (A). Let us consider the first repeated block:

[ //a_1, \ldots, a_m, t_1, \ldots// = \frac{K_{2m+1}(a_1, \ldots, a_m, t_1, a_1, \ldots, a_m)}{K_{2m}(t_1, a_1, \ldots, a_m)}. ]

Multiplying by (K_m) gives

[ K_m \cdot //a_1, \ldots, a_m, t_1, a_1, \ldots, a_m// = \frac{K_m K_{2m+1}(a_1, \ldots, a_m, t_1, a_1, \ldots, a_m)}{K_{2m}(t_1, a_1, \ldots, a_m)}. ]

By the concatenation formula,

[ K_{2m+1}(a_1, \ldots, a_m, t_1, a_1, \ldots, a_m) = K_m(a_1, \ldots, a_m) K_{m+1}(t_1, a_1, \ldots, a_m) + K_{m-1}(a_1, \ldots, a_{m-1}) K_m(a_2, \ldots, a_m). ]

The second term depends only on the (a_i) and (t_1), not on any (x_i).

Extending to the full infinite tail of (A), the dependence on (x_3, x_4, \ldots) appears only in the last factor (K_{*}(x_3, \ldots)) in both (A) and (B). After multiplying by (K_m), the expressions reduce to

[ K_m \cdot A = \text{(expression depending only on $a_1, \ldots, a_m$, $t_1$, $t_2$)} + K_m \cdot (\text{tail depending on $x_3, x_4, \ldots$}), ]

[ K_m \cdot B = \text{(same tail-dependent factor)}. ]

Because the tail of (x_3, x_4, \ldots) is multiplied by the same (K_m) in both (A) and (B), it cancels in the difference:

[ K_m \cdot (A - B) = \text{expression depending only on $a_1, \ldots, a_m$, $t_1$, $t_2$}. ]

Step 3: Conclude independence of the tail variables

Since (K_m(a_1, \ldots, a_m) \neq 0), we divide both sides by (K_m) to recover

[ A - B ]

as independent of (x_1, x_2, x_3, \ldots).

Explicitly, the difference depends only on the repeated blocks (a_1, \ldots, a_m) and the interleaving entries (t_1, t_2). Any sequence appended after the last complete block contributes identically to both continued fractions and cancels in the difference.

Step 4: Optional remark

This phenomenon is a general feature of repeated blocks in continued fractions: multiplication by the continuant of the block isolates the “core” contribution of the repeated segment, rendering any appended tail irrelevant in the difference with the reversed pattern.

Answer

[ //a_1, \ldots, a_m, t_1, a_1, \ldots, a_m, t_2, a_1, \ldots// - //a_m, \ldots, a_1, t_1, a_m, \ldots, a_1, t_2, \ldots// ]

is independent of (x_1, x_2, x_3, \ldots).