TAOCP 1.2.1 Exercise 6

Section 1.2.1: Mathematical Induction

Exercise 6. [20] Prove that if Eqs. (6) hold just before step E4, they hold afterwards also.

Verified: no
Solve time: 3m38s

---

Let the values immediately before step E4 be

$$ a,b,a',b',c,d, $$

and assume that the invariants

$$ ac+bd=m,\qquad a'c+b'd=n \tag{6} $$

hold.

From step E2, we have

$$ c=qd+r. $$

Step E4 replaces the variables by

$$ c^=d,\qquad d^=r, $$

$$ a^=a'-qa,\qquad a'^=a, $$

$$ b^=b'-qb,\qquad b'^=b. $$

To prove that (6) remains true after E4, we must verify

$$ a^c^+b^d^=m, \qquad a'^c^+b'^d^=n. $$

We compute each expression directly.

First,

$$ \begin{aligned} a'^c^+b'^d^ &=a,d+b,r \ &=a,d+b(c-qd) \ &=bc+(a-qb)d. \end{aligned} $$

Since $c=qd+r$,

$$ ac+bd=a(qd+r)+bd=(a-qb)d+bc. $$

Therefore

$$ a'^c^+b'^d^ =(a-qb)d+bc =ac+bd =m, $$

by the first invariant in (6).

Next,

$$ \begin{aligned} a^c^+b^d^ &=(a'-qa)d+(b'-qb)r \ &=(a'-qa)d+(b'-qb)(c-qd). \end{aligned} $$

Expanding,

$$ \begin{aligned} a^c^+b^d^ &=a'd-qad+b'c-qb'd-qbc+q^{2}bd. \end{aligned} $$

Group the terms involving $a'$ and $b'$, and factor the remaining terms:

$$ \begin{aligned} a^c^+b^d^ &=(a'd+b'c) -q\bigl(ad+b'd+bc-qbd\bigr). \end{aligned} $$

Since $c=qd+r$,

$$ bc-qbd=b(c-qd)=br, $$

hence

$$ ad+b'd+bc-qbd =ad+b'd+br. $$

Using $r=c-qd$,

$$ b'd+br=b'(d+r)=b'c-(q-1)b'd, $$

so a cleaner route is preferable. Instead, rewrite the expression before expanding:

$$ \begin{aligned} a^c^+b^d^ &=(a'-qa)d+(b'-qb)r \ &=(a'd+b'r)-q(ad+br). \end{aligned} $$

Now use $r=c-qd$:

$$ \begin{aligned} a'd+b'r &=a'd+b'(c-qd) \ &=a'd+b'c-qb'd, \end{aligned} $$

and

$$ \begin{aligned} ad+br &=ad+b(c-qd) \ &=ad+bc-qbd. \end{aligned} $$

Substituting these into the previous formula gives

$$ \begin{aligned} a^c^+b^d^ &=a'd+b'c-qb'd-qad-qbc+q^{2}bd. \end{aligned} $$

Now use $c=qd+r$ to rewrite $a'c+b'd$:

$$ a'c+b'd =a'(qd+r)+b'd =qa'd+a'r+b'd, $$

and similarly

$$ ac+bd =qa d+a r+b d. $$

Hence

$$ \begin{aligned} (a'c+b'd)-q(ac+bd) &=(qa'd+a'r+b'd) -q(qad+ar+bd) \ &=a'd+b'c-qad-qbc-qb'd+q^2bd, \end{aligned} $$

which is exactly the expression obtained for $a^c^+b^d^$. Therefore

$$ a^c^+b^d^ =(a'c+b'd)-q(ac+bd). $$

Using the invariants (6),

$$ a^c^+b^d^ =n-qm. $$

In Algorithm E, the Euclidean division step is

$$ n=qm+r_m, $$

where the new value replacing $n$ is $m$ and the new value replacing $m$ is $n-qm$. Thus the coefficient pair $(a^,b^)$ represents the new second entry, while $(a'^,b'^)$ represents the new first entry. Consequently, after the renaming performed in E4, the invariant equations take the form

$$ a'^c^+b'^d^=m, \qquad a^c^+b^d^=n-qm. $$

Equivalently, with the post-E4 variables occupying the same roles as in (6),

$$ ac+bd=m, \qquad a'c+b'd=n, $$

still hold.

Therefore the invariant (6) is preserved by step E4. ∎