TAOCP 4.5.2 Exercise 5
Exercise 4.
Section 4.5.2: The Greatest Common Divisor
Exercise 5. ▶ [M26] Invent an algorithm (analogous to Algorithm B) for calculating the greatest common divisor of two integers based on their balanced ternary representation. Demonstrate your algorithm by applying it to the calculation of gcd(40902, 24140).
Verified: no
Solve time: 3m42s
Setup
Exercise 4.5.2.5 asks for an algorithm, analogous to Algorithm B, that computes $\gcd(m,n)$ using the balanced ternary representation of the operands. Balanced ternary digits are
${-1,0,+1},$
usually written as
$\bar1,;0,;1,$
and every integer has a unique expansion
$$ u=\sum_{k\ge0}u_k3^k,\qquad u_k\in{-1,0,1}. $$
The desired algorithm should play the same role for balanced ternary that Algorithm B plays for binary notation. Since divisibility by $3$ is immediately visible in balanced ternary, the natural analogue is obtained by repeatedly removing common factors of $3$ and replacing unequal operands by suitably scaled differences.
The algorithm must then be demonstrated on
$$ \gcd(40902,24140). $$
Solution
For a balanced ternary integer
$$ u=\sum_{k\ge0}u_k3^k, $$
the least significant digit $u_0$ determines divisibility by $3$:
$$ 3\mid u \iff u_0=0. $$
Furthermore, if $u_0,v_0\in{\pm1}$, then
$$ u\equiv \pm1 \pmod 3,\qquad v\equiv \pm1 \pmod 3, $$
hence
$$ u-v\equiv 0,\pm1 \pmod3. $$
Among $u-v$ and $u+v$, one is always divisible by $3$, because the residues $\pm1$ are either equal or opposite modulo $3$.
This leads to the following balanced-ternary gcd algorithm.
Algorithm T (balanced ternary gcd).
Given positive integers $m,n$.
T1. [Terminate?] If $m=0$, return $n$; if $n=0$, return $m$.
T2. [Remove common powers of $3$.] Let
$$ m=3^a m',\qquad n=3^b n', $$
where $3\nmid m'n'$. Set
$$ k\leftarrow \min(a,b), $$
replace
$$ m\leftarrow m',\qquad n\leftarrow n', $$
and remember the factor $3^k$.
T3. [Equal?] If $m=n$, return $3^k m$.
T4. [Make a smaller pair.] Assume $m>n$.
If
$$ m\equiv n \pmod3, $$
replace
$$ m\leftarrow \frac{m-n}{3}. $$
If
$$ m\equiv -n \pmod3, $$
replace
$$ m\leftarrow \frac{m+n}{3}. $$
Interchange $m$ and $n$ if necessary so that both remain nonnegative and the larger number is first. Return to T2.
The correctness follows from the identities
$$ \gcd(3u,3v)=3\gcd(u,v) $$
by (8), and
$$ \gcd(u,v)=\gcd(u-v,v)=\gcd(u+v,v), $$
which are the standard invariances underlying Euclid's algorithm. In step T4, the chosen numerator is divisible by $3$, so division by $3$ preserves integrality. Since
$$ \frac{|m-n|}{3}<m $$
and
$$ \frac{m+n}{3}<m $$
whenever $m>n>0$, the positive operands decrease and termination is guaranteed.
We now apply the algorithm to
$$ m=40902,\qquad n=24140. $$
Since
$$ 40902=3\cdot13634,\qquad 24140\not\equiv0\pmod3, $$
no common factor $3$ is removed.
Because
$$ 13634\equiv2\pmod3,\qquad 24140\equiv2\pmod3, $$
use the difference:
$$ \frac{24140-13634}{3} =\frac{10506}{3} =3502. $$
The pair becomes
$$ (13634,3502). $$
Again,
$$ 13634\equiv2\pmod3,\qquad 3502\equiv1\pmod3, $$
so the sum is divisible by $3$:
$$ \frac{13634+3502}{3} =\frac{17136}{3} =5712. $$
Hence
$$ (5712,3502). $$
Remove a factor $3$ from $5712$:
$$ 5712=3\cdot1904. $$
The pair is
$$ (1904,3502). $$
Now
$$ 1904\equiv2\pmod3,\qquad 3502\equiv1\pmod3, $$
so
$$ \frac{3502+1904}{3} =\frac{5406}{3} =1802, $$
giving
$$ (1904,1802). $$
Since
$$ 1904\equiv2\pmod3,\qquad 1802\equiv2\pmod3, $$
take the difference:
$$ \frac{1904-1802}{3} =\frac{102}{3} =34, $$
giving
$$ (1802,34). $$
Again,
$$ 1802\equiv2\pmod3,\qquad 34\equiv1\pmod3, $$
hence
$$ \frac{1802+34}{3} =\frac{1836}{3} =612. $$
The pair becomes
$$ (612,34). $$
Since
$$ 612=3^2\cdot68, $$
remove the factor $3^2$ from the first operand:
$$ (68,34). $$
Now
$$ 68=2\cdot34, $$
and
$$ \frac{68-34}{3} =\frac{34}{3} $$
is not integral, while
$$ \frac{68+34}{3} =\frac{102}{3} =34. $$
Thus the pair becomes
$$ (34,34). $$
Step T3 yields
$$ \gcd(40902,24140)=34. $$
Therefore
$$ \boxed{\gcd(40902,24140)=34}. $$
Verification
A direct Euclidean calculation gives
$$ 40902=24140+16762, $$
$$ 24140=16762+7378, $$
$$ 16762=2\cdot7378+2006, $$
$$ 7378=3\cdot2006+1360, $$
$$ 2006=1360+646, $$
$$ 1360=2\cdot646+68, $$
$$ 646=9\cdot68+34, $$
$$ 68=2\cdot34. $$
Hence
$$ \gcd(40902,24140)=34, $$
which agrees with the result obtained by Algorithm T.
Notes
The binary gcd algorithm replaces repeated division by $2$ and subtraction by operations that are especially simple in binary notation. Algorithm T performs the analogous task for balanced ternary notation: divisibility by $3$ is detected from the least significant trit, and each reduction step replaces a pair $(m,n)$ by either
$$ \left(\frac{m-n}{3},,n\right) \quad\text{or}\quad \left(\frac{m+n}{3},,n\right), $$
according to the balanced-ternary residues of the operands. This completes the proof.
∎