Question

the following is the euclid 2,300 year old algorithm for fining the greatest common divisorof two positive integers I an J

step Operation

1. get two positive integers as input; call the larger value I and the smaller value J.

2. Divide I by J, and call rhe remainder R.

3. If R is no 0, then reset I to the value of J, reset J to the cslue of R, and go back to step 2

4. print out the answer , which the value of J.

5 stop.

go throw the algorithm using the input value 20 and 32 . After each step of the algorithm completed, give the value of I,J abd R. Determine the final output of the algorithm.

Answer 1

Euclid’s algorithm to find the greatest common divisor

Algorithm for finding the greatest common divisor of two positive integers “ I ” and “ J ”:

Step 1: Assign the larger integer input value as “I” and smaller integer input value as “J”.

Step 2: Divide the value of “I” with the value of “J” and set the remainder to “R”.

Step 3: If the value of “R” is not equal to zero, then assign the value of “J” to “I” and assign the value of “R” to “J” and go to step 2.

Step 4: Print the value of “J” as the greatest common divisor.

Step 5: Stop the process.

a) Analyze the above “Euclid’s algorithm” with the inputs 20 and 32 and trace the values of “ I ”, “ J ”, and “ R ” after completing each step.

• Step 1: Assign the larger value 32 to “I” and smaller value 20 to “J”.

Value of “I”	32
Value of “J”	20
Value of “R”	Not assigned

Step 2:

-> Divide the value of “I” with the value of “J” and set the remainder to

“R”.

-> Dividing 32 by 20 gives the quotient as 1 and remainder “R” as 12.

Value of “I”	32
Value of “J”	20
Value of “R”	12

Step 3:

-> If the value of “R” is not equal to zero, then assign the value of “J” to “I” and assign the value of “R” to “J” and go to step 2.

-> The value of “R” is 12, which is not equal to 0. So, “I” becomes 20 and “J” becomes 12 and go to step 2.

Value of “I”	20
Value of “J”	12
Value of “R”	12

Moved to Step 2:

• Step 2:

-> Divide the value of “I” with the value of “J” and set the remainder to “R”.

-> Dividing 20 by 12 gives the quotient as 1 and remainder “R” as 8.

Value of “I”	20
Value of “J”	12
Value of “R”	8

• Step 3:

-> As the value of “R” is 8, which is not equal to 0. So, “I” becomes 12 and “J” becomes 8.

Value of “I”	12
Value of “J”	8
Value of “R”	8

Next iteration of step 2:

• Step 2:

-> Divide the value of “I” with the value of “J” and set the remainder to “R”.

-> Dividing 12 by 8 gives the quotient as 1 and remainder “R” as 4.

Value of “I”	12
Value of “J”	8
Value of “R”	4

Step 3:

-> As the value of “R” is 4, which is not equal to 0. So, “I” becomes 8 and “J” becomes 4.

Value of “I”	8
Value of “J”	4
Value of “R”	4

Next iteration of step 2:

• Step 2:

-> Divide the value of “I” with the value of “J” and set the remainder to “R”.

-> Dividing 8 by 4 gives the quotient as 2 and remainder “R” as 0.

-> As the value of “R” becomes 0, go to step 4.

Value of “I”	8
Value of “J”	4
Value of “R”	0

• Step 4:

-> Print the answer.

-> Hence, the greatest common divisor of 32 and 20 is 4.

• Step 5:

-> Stop the process.

Therefore, the “Euclid’s algorithm” determines the greatest common divisor among two positive integers 32 and 20 as .