Solution Found!
An alternative to the Euclidean algorithm uses subtraction
Chapter 4, Problem 24E(choose chapter or problem)
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.8.3
If a \(\geq\) b > 0, then gcd(a, b) = gcd(b, a − b).
a. Prove Lemma 4.8.3.
b. Trace the execution of Algorithm 4.8.3 for A = 630 and B = 336.
c. Trace the execution of Algorithm 4.8.3 for A = 768 and B = 348.
Text Transcription:
geq
Questions & Answers
QUESTION:
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.8.3
If a \(\geq\) b > 0, then gcd(a, b) = gcd(b, a − b).
a. Prove Lemma 4.8.3.
b. Trace the execution of Algorithm 4.8.3 for A = 630 and B = 336.
c. Trace the execution of Algorithm 4.8.3 for A = 768 and B = 348.
Text Transcription:
geq
ANSWER:Solution:Step 1:Here we have to prove that, if a b > 0, then gcd(a, b) = gcd(b, a b). Also trace the execution of Algorithm 4.8.3 for given values of and .