Question

How many steps does Euclid's algorithm go through when 1729 and 729 are given as inputs to it? It halts when one of the arguments is zero.

 4

 6

 9

 10​

Answer 1

Answer:

Explanation:6 steps maximum

Answer 2

Answer:

9 steps

Explanation:

step 1

1729 mod 729 = 271

step 2

729 mod 271 = 187  

step 3

271 mod 187 = 84

step 4

187 mod 84 = 19

step 5

84 mod 19 = 8

step 6

19 mod 8 = 3

step 7

8 mod 3 = 2

step 8

3 mod 2 = 1

step 9

2 mod 1 = 0