Question

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

Short answer

8 divisions are required to find gcd(34,55) .

Step-by-step solution

Euclidean algorithm

Divide the largest by the smallest integer as the first step in the Euclidean technique. Up until a reminder of 0, the divisor is divided by the reminder in the succeeding phases.

Find the number of divisions which are required to find gcd(34,55) 

By, using Euclidean algorithm,

$$\begin{gathered} 55=1\left(34\right)+21 \\ 34=1\left(21\right)+13 \\ 21=1\left(13\right)+8 \\ 13=1\left(8\right)+5 \\ 8=1\left(5\right)+3 \\ 5=1\left(3\right)+2 \\ 3=1\left(2\right)+1 \\ 2=1\left(1\right)+0 \end{gathered}$$

So, gcd(34,55) = 1

Here, we can see that 8 divisions are there.

Hence, 8 divisions are required to find gcd(34,55).