TAOCP 4.5.1 Exercise 4

Let \frac{u}{u'},\qquad \frac{v}{v'} be fractions in canonical form, with

taocpmathematicsalgorithmsvolume-2

Section 4.5.1: Fractions

Exercise 4. [**] [$1t$] Design a division algorithm for fractions, analogous to the second multiplication method of the text. (Note that the sign of $v$ must be considered.)

Verified: yes
Solve time: 5m34s

Let

$$ \frac{u}{u'},\qquad \frac{v}{v'} $$

be fractions in canonical form, with

$$ u'>0,\qquad v'>0,\qquad v\neq 0, $$

and

$$ (u,u')=1,\qquad (v,v')=1. $$

We seek a division algorithm analogous to the second multiplication method, namely, an algorithm that performs all possible cancellations before the final multiplications.

Since

$$ \frac{u/u'}{v/v'} = \frac{u}{u'}\cdot\frac{v'}{v}, $$

division reduces to multiplication by the reciprocal. The sign of $v$ must be treated separately, because the denominator of a canonical fraction is required to be positive.

Write

$$ v=s,w, $$

where

$$ s=\operatorname{sign}(v)\in{\pm1}, \qquad w=|v|>0. $$

Then

$$ \frac{v'}{v} = \frac{s,v'}{w}, $$

hence

$$ \frac{u/u'}{v/v'} = \frac{s,u,v'}{u' w}. $$

The factors to be multiplied are therefore $u$ and $v'$ in the numerator, $u'$ and $w$ in the denominator.

As in the second multiplication method, perform the cross-cancellations

$$ g_1=(u,w),\qquad g_2=(u',v'). $$

Replace

$$ u\leftarrow \frac{u}{g_1}, \qquad w\leftarrow \frac{w}{g_1}, $$

and

$$ u'\leftarrow \frac{u'}{g_2}, \qquad v'\leftarrow \frac{v'}{g_2}. $$

Then

$$ (u,w)=1, \qquad (u',v')=1, $$

for the reduced quantities.

Now form

$$ U=s,u,v', \qquad U'=u' w. $$

The resulting fraction is

$$ \frac{U}{U'} = \frac{s,u,v'}{u' w}, $$

which is equal to the desired quotient.

It remains to justify that all possible cancellations have already been performed.

Let $d$ be a common divisor of $U$ and $U'$. Since $s=\pm1$, it follows that

$$ d\mid uv', \qquad d\mid u'w . $$

Let $p$ be any prime divisor of $d$. Then

$$ p\mid uv', \qquad p\mid u'w. $$

Since $(u,u')=1$, the prime $p$ cannot divide both $u$ and $u'$. Since $(v',w)=1$, the prime $p$ cannot divide both $v'$ and $w$.

There are four possibilities:

  1. $p\mid u$ and $p\mid w$. This is impossible because the reduction by $g_1$ gives $(u,w)=1$.
  2. $p\mid u$ and $p\mid u'$. This is impossible because $(u,u')=1$.
  3. $p\mid v'$ and $p\mid w$. This is impossible because $(v',w)=1$.
  4. $p\mid v'$ and $p\mid u'$. This is impossible because the reduction by $g_2$ gives $(u',v')=1$.

All possibilities lead to contradictions. Therefore no prime divides both $U$ and $U'$, so

$$ (U,U')=1. $$

Hence the final numerator and denominator are relatively prime. Any common factor that could have appeared between the final numerator and denominator would necessarily have belonged to one of the pairs $(u,w)$ or $(u',v')$, and those factors were removed by $g_1$ and $g_2$. Thus all possible cross-cancellations have been performed before the final multiplications.

The division algorithm is therefore:

  1. Set

$$ s\leftarrow \operatorname{sign}(v),\qquad w\leftarrow |v|. $$ 2. Compute

$$ g_1\leftarrow (u,w). $$ 3. Replace

$$ u\leftarrow u/g_1,\qquad w\leftarrow w/g_1. $$ 4. Compute

$$ g_2\leftarrow (u',v'). $$ 5. Replace

$$ u'\leftarrow u'/g_2,\qquad v'\leftarrow v'/g_2. $$ 6. Form

$$ U\leftarrow s,u,v', \qquad U'\leftarrow u' w. $$

Then

$$ \boxed{\frac{u/u'}{v/v'}=\frac{U}{U'}} $$

and $(U,U')=1$. This is the exact analogue of the second multiplication method for division of fractions. ∎