Question

How many divisions are required to find ged (21,34) using the Euclidean algorithm ? This problem is NOT asking you to find god (21,34).

(a) 10
(b) 9
(c) 8
(d) 7
(e) 6

Answer 1

To find gcd(21, 34) using the Euclidean algorithm, we need 6 divisions.

Step-by-step explanation:

To find the gcd (21, 34) using the Euclidean algorithm, we start by dividing 34 by 21. This gives us a quotient of 1 and a remainder of 13. Next, we divide 21 by 13, which gives us a quotient of 1 and a remainder of 8. We continue this process until we reach a remainder of 0. The number of divisions required is equal to the number of steps taken, which in this case is 6. Therefore, the answer is (e).