The following is Euclid\'s 2,300 year old algorithm for findingthe greast common

Question

The following is Euclid's 2,300 year old algorithm for findingthe greast common divisor of two positive integers I and J. Step   Operation 1        Get twopositive integers as input. Call the larger value I and the smallervalue J. 2        Divide I byJ, and call the remainder R. 3        If R is not0, then reset I to the value of J, reset J to the value of R, andgo back to step 2. 4        Print out theanswer, which is the value of J. 5        Stop. Go through this algorithm (trace) with input values 32 and 5.You will execute Step-3 several times; After everyexecution/completion of step-3 state values of I,J and R. What isthe final answer printed by this algorithm? The following is Euclid's 2,300 year old algorithm for findingthe greast common divisor of two positive integers I and J. Step   Operation 1        Get twopositive integers as input. Call the larger value I and the smallervalue J. 2        Divide I byJ, and call the remainder R. 3        If R is not0, then reset I to the value of J, reset J to the value of R, andgo back to step 2. 4        Print out theanswer, which is the value of J. 5        Stop. Go through this algorithm (trace) with input values 32 and 5.You will execute Step-3 several times; After everyexecution/completion of step-3 state values of I,J and R. What isthe final answer printed by this algorithm?

Explanation / Answer

1) I = 32, J=5 2) dividing I/J gives R =2 3) R is not 0...therefore I= 5, J=2..invokes step 2 again     2) R =1 (when 5 is divided by 2)     3)   R is not 0, therefore I=2, J=1invokes step-2 again           2) R =0 when I dividedby J           3) R =0 therefore wontgo to step-2 4) Answer is J=1 5) Stop Therefore the final answer is J=1 Therefore GCD(32,5) is 1

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.