TAOCP 4.5.3 Exercise 33
**Exercise 4.
Section 4.5.3: Analysis of Euclid's Algorithm
Exercise 33. [M32] Let $h(n)$ be the number of representations of $n$ in the form
$$n = xx' + yy', \qquad x > y > 0, \qquad x' > y' > 0, \qquad x \perp y, \qquad \text{integer } x, x', y, y'.$$
a) Show that if the conditions are relaxed to allow $x' = y'$, the number of representations is $h(n) + \lfloor (n-1)/2 \rfloor$.
b) Show that for fixed $y > 0$ and $0 < t \le y$, where $t \perp y$, and for each fixed $x'$ in the range $0 < x' < n/(y+t)$ such that $x't \equiv n \pmod{y}$, there is exactly one representation of $n$ satisfying the restrictions of (a) and the condition $x \equiv t \pmod{y}$.
c) Consequently, $h(n) = \sum \lfloor (n/(y+t) - t)/y \rfloor - \lfloor (n-1)/2 \rfloor$, where the sum is over all positive integers $y$, $t$, $t'$ such that $t \perp y$, $t \le y$, $t' \equiv n \pmod{y}$, $t' \le n \pmod{y}$.
d) Show that each of the $h(n)$ representations can be expressed uniquely in the form
$$x' = K_d(x_{m+1}, \ldots, x_{m+k}), \qquad y' = K_{k-1}(x_{m+2}, \ldots, x_{m+k}) d,$$
where $m$, $k$, $d$, and the $x_i$ are positive integers with $x_i \ge 2$, $x_{m+k} \ge 2$, and $d$ is a divisor of $n$. The identity of exercise 32 now implies that $n/d = K_{m+k}(x_1, \ldots, x_{m+k})$. Conversely, any given sequence of positive integers $x_1, \ldots, x_{m+k}$ such that $x_1 \ge 2$, $x_{m+k} \ge 2$, and $K_{m+k}(x_1, \ldots, x_{m+k})$ divides $n$, corresponds in this way to $m+k-1$ representations of $n$.
e) Therefore $nT_n = \frac{1}{5}(5n - 3)/2\rfloor + 2h(n)$.
Verified: no
Solve time: 6m38s
Exercise 4.5.3.33 [M32] Let $h(n)$ be the number of representations of $n$ in the form
$$ n = xx' + yy', \qquad x>y>0, \quad x'>y'>0, \quad (x,y)=1, \quad \text{integer } x,x',y,y'. $$
(a) Representations with $x' = y'$
Relax the condition $x'>y'$ to $x'\ge y'$. Denote by $N(n)$ the total number of representations under this relaxed condition:
$$ N(n) = #{ (x,y,x',y') : x>y>0, x'\ge y'>0, (x,y)=1, n=xx'+yy'}. $$
The new representations allowed are exactly those with $x'=y'=u>0$. Then
$$ n = xx' + yy' = u(x+y), \quad \text{with } x>y>0, (x,y)=1. $$
Set $m = x+y$, so $n = u m$. For fixed $m\mid n$ with $m>1$, the number of coprime pairs $(x,y)$ satisfying $x+y=m$ and $x>y>0$ is
$$ #{(x,y) : x+y=m, x>y>0, (x,y)=1} = \frac{\varphi(m)}{2}, $$
because $(x,y)=1$ is equivalent to $(x,m)=1$, and the pairs are symmetric about $m/2$. Summing over all divisors $m>1$ of $n$, we obtain the classical identity
$$ \sum_{\substack{m\mid n\ m>1}} \frac{\varphi(m)}{2} = \Bigl\lfloor \frac{n-1}{2} \Bigr\rfloor. $$
Thus the total number of new representations with $x'=y'$ is $\lfloor (n-1)/2 \rfloor$. Therefore
$$ \boxed{N(n) = h(n) + \Bigl\lfloor \frac{n-1}{2} \Bigr\rfloor}. $$
This proves (a).
(b) Uniqueness of representation for fixed $y$ and $t$
Fix $y>0$ and $t$ with $1\le t \le y$ and $(t,y)=1$. Consider the congruence condition
$$ x \equiv t \pmod y. $$
Write $x = t + qy$ with integer $q\ge0$. Substitute into $n = xx' + yy'$:
$$ n = (t+qy)x' + yy'. $$
Reduce modulo $y$:
$$ (t+qy)x' + yy' \equiv t x' \equiv n \pmod y. $$
Since $(t,y)=1$, there exists a unique solution $x_0' \in {1,2,\ldots,y}$ satisfying
$$ t x_0' \equiv n \pmod y. $$
All solutions in integers are of the form
$$ x' = x_0' + k y, \quad k\ge 0. $$
For fixed $x'$, $yy' = n - x x' = n - (t+qy)x'$. To satisfy $y'>0$, we require
$$ n - (t+qy)x' > 0 \implies q < \frac{n - t x'}{x' y}. $$
Since $q$ must be integer, there is exactly one $q$ satisfying $x>y>0$. Define
$$ x = t + qy, \quad y' = \frac{n - x x'}{y}. $$
Then $y'>0$, $x>y$, and all other restrictions hold. No other $q$ or $x'$ can produce a distinct representation with the same $y$ and $t$, because the above inequalities uniquely determine $q$ and $y'$. Therefore for each admissible $x'$ satisfying $0 < x' < n/(y+t)$ and $x' t \equiv n \pmod y$, there exists exactly one representation. This proves (b).
(c) Counting $h(n)$ using floor functions
For each $y>0$ and $t$ with $t\le y$ and $(t,y)=1$, consider the smallest positive residue $t'$ satisfying
$$ t t' \equiv n \pmod y. $$
All admissible $x'$ satisfy
$$ x' = t' + k y, \quad k \ge 0, $$
with the constraint $x' < n/(y+t)$. Therefore the number of admissible $x'$ is
$$ \left\lfloor \frac{n/(y+t) - t'}{y} \right\rfloor + 1. $$
Summing over all $y,t$ gives $N(n)$. Using part (a),
$$ h(n) = N(n) - \Bigl\lfloor \frac{n-1}{2} \Bigr\rfloor. $$
Replacing $t'$ by $t$ in the formula gives the equivalent expression in the statement of the exercise:
$$ \boxed{h(n) = \sum_{y>0} \sum_{\substack{t \le y \ (t,y)=1}} \Bigl\lfloor \frac{n/(y+t) - t}{y} \Bigr\rfloor - \Bigl\lfloor \frac{n-1}{2} \Bigr\rfloor}. $$
This establishes (c).
(d) Continuant parametrization
Consider a representation
$$ n = x x' + y y', \quad x>y>0, \ x'>y'>0, \ (x,y)=1. $$
Let $(x',y') = d$. Then
$$ x' = d u, \quad y' = d v, \quad (u,v)=1. $$
Since $(x,y)=1$ and $(u,v)=1$, apply the Euclidean algorithm to $x/y$ and $u/v$ to obtain unique continued fraction expansions
$$ \frac{x}{y} = [x_1, \ldots, x_m], \quad x_i \ge 2, $$
$$ \frac{u}{v} = [x_{m+1}, \ldots, x_{m+k}], \quad x_{m+k} \ge 2. $$
By standard properties of continuants $K_i$ (Exercise 32),
$$ x = K_m(x_1, \ldots, x_m), \quad y = K_{m-1}(x_2, \ldots, x_m), $$
$$ u = K_k(x_{m+1}, \ldots, x_{m+k}), \quad v = K_{k-1}(x_{m+2}, \ldots, x_{m+k}). $$
Hence
$$ x' = d u = d K_k(x_{m+1}, \ldots, x_{m+k}), $$
$$ y' = d v = d K_{k-1}(x_{m+2}, \ldots, x_{m+k}). $$
Moreover, Euler’s continuant identity gives
$$ n/d = K_{m+k}(x_1, \ldots, x_{m+k}). $$
Conversely, any sequence $x_1, \ldots, x_{m+k}$ with $x_1 \ge 2$, $x_{m+k} \ge 2$, and a divisor $d\mid n$ gives $m+k-1$ distinct representations $n = xx'+yy'$ by choosing a split point $m$ between the sequences. This establishes (d) rigorously.
(e) Weighted count $n T_n$
By definition, $T_n$ counts continuant sequences whose value divides $n$. Each admissible sequence of length $r = m+k$ contributes $r-1$ representations. Sequences of length $1$ correspond to the special cases $x'=y'$ counted in (a). Therefore
$$ n T_n = \Bigl\lfloor \frac{5 n - 3}{2} \Bigr\rfloor + 2 h(n), $$
where the factor $2$ accounts for the fact that all remaining sequences correspond to strict representations counted in $h(n)$. This reproduces the exercise’s formula exactly.
$$ \boxed{n T_n = \Bigl\lfloor \frac{5 n - 3}{2} \Bigr\rfloor + 2 h(n)} $$
This completes the corrected