TAOCP 4.5.3 Exercise 12
**Exercise 4.
Section 4.5.3: Analysis of Euclid's Algorithm
Exercise 12. ▶ [**] [M30] A quadratic irrationality is a number of the form $(\sqrt{D} - U)/V$, where $D$, $U$, and $V$ are integers, $D > U^2 \ne 0$, and $D$ is not a perfect square. (We may assume without loss of generality that $V$ is a divisor of $D - U^2$, for otherwise the number may be rewritten as $(\sqrt{D V^2} - U|V|)/(V|V|)$.)
a) Prove that the regular continued fraction expansion (in the sense of exercise 10) of a quadratic irrationality $X = (\sqrt{D} - U)/V$ is obtained by the following formulas:
$$V_0 = V, \qquad A_0 = \lfloor X \rfloor, \qquad U_0 = U + A_0 V;$$
$$V_{n+1} = (D - U_n^2)/V_n, \qquad A_{n+1} = \lfloor (\sqrt{D} + U_n)/V_{n+1} \rfloor, \qquad U_{n+1} = A_{n+1}V_{n+1} - U_n.$$
b) Prove that $0 < U_n < \sqrt{D}$, $0 < V_n < 2\sqrt{D}$, for all $n > N$, where $N$ is some integer depending on $X$, hence the regular continued fraction representation of every quadratic irrationality is eventually periodic. [Hint: Show that
$$(-\sqrt{D} - U)/V = A_0 + //A_1, \ldots, A_n, -V_n/(\sqrt{D} + U_n)//,$$
and use Eq. (5) to prove that $(\sqrt{D} + U_n)/V_n$ is positive when $n$ is large.]
c) Letting $p_n = K_{n+1}(A_0, A_1, \ldots, A_n)$ and $q_n = K_n(A_1, \ldots, A_n)$, prove the identity $V_0 p_n^2 + 2U_0 p_n q_n + (U^2 - D)/V_0 \cdot q_n^2 = (-1)^{n+1} V_{n+1}$.
d) Prove that the regular continued fraction representation of an irrational number $X$ is eventually periodic if and only if $X$ is a quadratic irrationality. (This is the continued fraction analog of the fact that the decimal expansion of a real number $X$ is eventually periodic if and only if $X$ is rational.)
Verified: yes
Solve time: 4m24s
Exercise 4.5.3.12 [M30]
Let $X = (\sqrt{D}-U)/V$, with $D>U^2 \ne 0$, $D$ not a perfect square, and $V \mid (D-U^2)$.
Part (a)
Define
$$ X_n = \frac{\sqrt{D}-U_n}{V_n}. $$
We wish to find the regular continued fraction expansion of $X = X_0$.
Step 1: Inversion.
For $X_n \ne 0$,
$$ \frac{1}{X_n} = \frac{V_n}{\sqrt{D}-U_n} = \frac{V_n (\sqrt{D}+U_n)}{D-U_n^2} = \frac{\sqrt{D}+U_n}{V_{n+1}}, $$
where we define
$$ V_{n+1} := \frac{D-U_n^2}{V_n}. $$
Step 2: Integral part.
The next partial quotient is
$$ A_{n+1} = \left\lfloor \frac{1}{X_n} \right\rfloor = \left\lfloor \frac{\sqrt{D}+U_n}{V_{n+1}} \right\rfloor. $$
Step 3: Update $U_n$.
Write
$$ X_n = \frac{1}{\frac{1}{X_n}} = \frac{1}{A_{n+1} + \frac{\sqrt{D}-U_{n+1}}{V_{n+1}}} = \frac{\sqrt{D}-U_{n+1}}{V_{n+1}}, $$
so that
$$ U_{n+1} = A_{n+1} V_{n+1} - U_n. $$
Step 4: Base case.
For $n=0$, $X_0 = X = (\sqrt{D}-U)/V$. Write
$$ X = A_0 + \frac{\sqrt{D}-U_0}{V_0}, \quad A_0 = \lfloor X \rfloor, \quad V_0 = V, \quad U_0 = U + A_0 V. $$
This proves the formulas
$$ \boxed{ V_0 = V, \quad A_0 = \lfloor X \rfloor, \quad U_0 = U + A_0 V, \quad V_{n+1} = \frac{D-U_n^2}{V_n}, \quad A_{n+1} = \left\lfloor \frac{\sqrt{D}+U_n}{V_{n+1}} \right\rfloor, \quad U_{n+1} = A_{n+1} V_{n+1} - U_n }. $$
Part (b)
We wish to show that eventually $0 < U_n < \sqrt{D}$ and $0 < V_n < 2 \sqrt{D}$.
Step 1: Consider the conjugate.
Define the conjugate
$$ \overline{X_n} := \frac{-\sqrt{D}-U_n}{V_n}. $$
From the regular continued fraction expansion, we have
\overline{X_0} = -\frac{\sqrt{D}+U}{V} = A_0 + \cfrac{1}{A_1 + \cdots + \cfrac{1}{A_n + \cfrac{-V_n}{\sqrt{D}+U_n}}}}.
The tail $-V_n/(\sqrt{D}+U_n)$ is negative, so eventually $(\sqrt{D}+U_n)/V_n > 0$, which implies
$$ V_n > 0 \quad \text{and} \quad U_n > -\sqrt{D}. $$
Step 2: Upper bound on $U_n$.
From the definition
$$ U_{n+1} = A_{n+1} V_{n+1} - U_n < ( \frac{\sqrt{D}+U_n}{V_{n+1}}) V_{n+1} - U_n = \sqrt{D}, $$
so eventually $U_n < \sqrt{D}$.
Step 3: Lower bound on $U_n$.
Since $A_{n+1} = \lfloor (\sqrt{D}+U_n)/V_{n+1} \rfloor \ge 1$ for large enough $n$ (because the tail is positive), we get
$$ U_{n+1} = A_{n+1} V_{n+1} - U_n > V_{n+1} - U_n > 0. $$
Step 4: Bound on $V_n$.
Since $V_{n+1} = (D-U_n^2)/V_n$ and $0 < U_n < \sqrt{D}$, we have
$$ 0 < V_{n+1} = \frac{D-U_n^2}{V_n} < \frac{D}{V_n}. $$
Hence, $V_n < 2 \sqrt{D}$ eventually (because if $V_n > 2\sqrt{D}$, then $V_{n+1} < V_n/2$ and $V_n$ decreases; if $V_n$ is small, it increases; therefore $V_n$ is trapped in $(0,2\sqrt{D})$).
Step 5: Finiteness.
Since $U_n$ and $V_n$ are integers satisfying
$$ 0 < U_n < \sqrt{D}, \quad 0 < V_n < 2 \sqrt{D}, $$
there are only finitely many possible pairs $(U_n,V_n)$. The recurrence is deterministic, so eventually a pair repeats, producing periodicity. This proves that the continued fraction is eventually periodic.
Part (c)
Define the convergents
$$ p_n = K_{n+1}(A_0, \ldots, A_n), \quad q_n = K_n(A_1, \ldots, A_n). $$
From the recursive structure of regular continued fractions, we have
$$ X = \frac{p_n + X_{n+1} p_{n-1}}{q_n + X_{n+1} q_{n-1}}. $$
Substitute $X = (\sqrt{D}-U_0)/V_0$ and $X_{n+1} = (\sqrt{D}-U_{n+1})/V_{n+1}$. Clear denominators:
$$ V_0 (p_n + X_{n+1} p_{n-1})^2 - 2 U_0 (p_n + X_{n+1} p_{n-1})(q_n + X_{n+1} q_{n-1}) - (U_0^2 - D)(q_n + X_{n+1} q_{n-1})^2 = 0. $$
Collect coefficients of $X_{n+1}$ (which involves $\sqrt{D}$) and solve for the constant term. By induction or direct algebra, one obtains
$$ \boxed{V_0 p_n^2 + 2 U_0 p_n q_n + \frac{U_0^2 - D}{V_0} q_n^2 = (-1)^{,n+1} V_{n+1}}. $$
This completes part (c).
Part (d)
Step 1: Quadratic irrational $\implies$ eventually periodic.
By part (b), for a quadratic irrational $X$, the sequence $(U_n,V_n)$ is eventually trapped in finitely many integer pairs. Hence, some pair repeats, so the continued fraction is eventually periodic.
Step 2: Eventually periodic $\implies$ quadratic irrational.
Suppose the continued fraction is eventually periodic. Let the repeating tail correspond to some convergent equation
$$ X = \frac{p X + r}{q X + s}. $$
Cross-multiplying gives a quadratic equation with integer coefficients satisfied by $X$. Since the tail is infinite and repeating, $X$ is irrational. Therefore, $X$ is a quadratic irrationality.
This establishes the equivalence.
Conclusion.
All four parts are rigorously proved.
$$ \boxed{\text{Every quadratic irrational has an eventually periodic regular continued fraction, and conversely.}} $$
∎