Chapter 4.10, Problem 27ES

An alternative to the Euclidean algorithm uses subtraction rather than division to compute greatest common divisors. (After all, division is repeated subtraction.) It is based on the following lemma.

Lemma 4.10.3

If $a\ge b>0$ , then $\gcd \left(a,b\right)=\gcd \left(b,a-b\right)$ .

Algorithm 4.10.3 Computlng gcd's by Subtraction [Given two positive integers A and B, variables a and b are set equal to A and B. Then a repetitive process begins. If $a\ne 0$, and $b\ne 0$ , then the larger of a and b is set equal to $a-b\left(ifa\ge b\right)$or to $b-a\left(ifa<b\right)$, and the smaller of a and b is left unchanged. This process is repeated over and over until eventually a or b becomes 0. By Lemma 4.10.3, after each repetition of the process,

$\gcd \left(A,B\right)=\gcd \left(a,b\right)$.

After the last repetition,

$\gcd \left(A,B\right)=\gcd \left(a,0\right)$or $\gcd \left(A,B\right)=\gcd \left(0,b\right)$depending on whether a or b is nonzero. But by Lemma 4.10.1,

$\gcd \left(a,0\right)=a$and $\gcd \left(0,b\right)=b$.

Hence, after the last repetition,

$\gcd \left(A,B\right)=a$if $a\ne 0$or $\gcd \left(A,B\right)=b$if $b\ne 0$.]

Input: A, B [positive integers]

Algorithm Body:

$a:=A$ , $b:=B$

while ( $a\ne 0$ and $b\ne 0$ )

if $a\ge b$ then $a:a-b$

else $b:=b-a$

end while

if a = 0 then $\gcd :=b$

else $\gcd :=a$

[After execution of the if—then-else statement, $\gcd =\gcd \left(A,B\right)$.]

Output: gcd [a positive integer]

a. Prove Lemma 4.10.3.

b. Trace the execution of Algorithm 4.10.3 for $A=630$ and $B=336$ .

c. Trace the Execution of Algorithm 4.10.3 for $A=768$ and $B=348$ .