TAOCP 4.5.3 Exercise 31
Let the modified algorithm of Exercise 30 be written in the form $u=qv+r,\qquad 0\le r<v,$ and replace the pair $(u,v)$ by $\bigl(v,\min(r,v-r)\bigr).$ Thus each division step uses the remainder of le...
Section 4.5.3: Analysis of Euclid's Algorithm
Exercise 31. ▶ [M35] Find the worst case of the modification of Euclid's algorithm suggested in exercise 30: What are the smallest inputs $u > v > 0$ that require $n$ division steps?
Verified: yes
Solve time: 1m53s
Setup
Let the modified algorithm of Exercise 30 be written in the form
$u=qv+r,\qquad 0\le r<v,$
and replace the pair $(u,v)$ by
$\bigl(v,\min(r,v-r)\bigr).$
Thus each division step uses the remainder of least absolute value modulo $v$. If
$r>\frac12v,$
the next value is $v-r$ instead of $r$.
Let $M_n$ denote the smallest value of $u$ for which the modified algorithm requires exactly $n$ division steps. We must determine the corresponding smallest pair $(u,v)$ with $u>v>0$.
Solution
The continued-fraction analysis used for Theorem F adapts naturally to this algorithm.
Suppose a division step begins with $(u,v)$ and produces $(v,w)$, where
$w=\min(r,v-r).$
Write
$$$$
If $r\le v/2$, then $w=r$ and
$$$$
If $r>v/2$, then $w=v-r$ and
$$$$
Hence every step admits a representation
$$$$
where $a\ge1$ is an integer and
$$$$
Conversely, every such representation produces the next pair $(v,w)$.
Assume that exactly $n$ division steps remain. Let $(u_n,v_n)$ be the pair at that stage and let
$$ \qquad 0<v_{n+1}\le \frac12v_n. $$
The algorithm then continues with $(v_n,v_{n+1})$. Therefore the smallest inputs yielding a prescribed number of remaining steps satisfy
$$$$
with all quantities as small as possible.
Since $u_n$ increases with $a_n$, the minimum occurs when
$$$$
For fixed $v_n$ and $v_{n+1}$, the choice
$$$$
is impossible because $u_n>v_n$ is required. Hence the smallest admissible value is
$$$$
Therefore the extremal pairs satisfy the recurrence
$$ \qquad u_{n+1}=v_n. $$
Writing
$$$$
the minimal sequence is determined by
$$$$
The terminal step occurs at $(2,1)$, since
$$$$
requires exactly one division. Thus
$$$$
Repeated use of
$$$$
generates
$$$$
namely the Fibonacci numbers. More precisely,
$$$$
Hence the smallest pair requiring $n$ division steps is
$$$$
These are exactly the pairs that occur in ordinary Euclid's algorithm.
To verify that such inputs indeed require $n$ steps under the modified procedure, observe that for consecutive Fibonacci numbers,
$$$$
so each division has quotient $1$ and remainder $F_k$. Since
$$$$
for all $k\ge2$, the modification never replaces the remainder by its complement. The sequence of pairs is therefore
$$ (F_{n+2},F_{n+1}), (F_{n+1},F_n), \ldots, (F_3,F_2), (F_2,F_1), $$
which contains exactly $n$ division steps.
Thus the worst case is unchanged.
Therefore the smallest inputs $u>v>0$ requiring exactly $n$ division steps are
$$ u=F_{n+2},\qquad v=F_{n+1}. $$
Hence
$$ \boxed{(u,v)=\bigl(F_{n+2},F_{n+1}\bigr)}. $$
Verification
For $n=1$ the formula gives
$$ (u,v)=(F_3,F_2)=(2,1), $$
which requires one division.
For $n=2$ it gives
$$ (u,v)=(F_4,F_3)=(3,2), $$
and
$$ (3,2)\to(2,1)\to(1,0), $$
so two divisions occur.
For $n=3$ it gives
$$ (u,v)=(5,3), $$
and
$$ (5,3)\to(3,2)\to(2,1)\to(1,0), $$
so three divisions occur.
The recurrence derived above generates exactly these extremal pairs, confirming the formula.
Notes
The modification of Exercise 30 improves the average behavior because remainders larger than $v/2$ are replaced by smaller complementary remainders. In the worst case, however, every remainder is already less than $v/2$. Consequently the modified algorithm follows exactly the same Fibonacci chain as ordinary Euclid's algorithm, and Theorem F remains valid without change.
This completes the proof.
∎