Problem 34E

How many divisions are required to find gcd(21, 34) using the Euclidean algorithm?

Solution:-

Step1

Given that

We have to find how many divisions are required to find gcd(21, 34) using the Euclidean algorithm?

Step2

We have

gcd(21, 34)

By using the Euclidean algorithm

Step3

As 1 is the last nonzero remainder

So, gcd(21, 34) is 1.

Therefore, 7 divisions are required to find gcd(21, 34) using the Euclidean algorithm.