MathNumber theory

Euclid's algorithm

Modifications

Report a typo

On each step of Euclid's algorithm, we replace the pair of positive arguments $(a, b)$ with $(b, a \bmod b)$ until one of arguments is zero. Consider three possible modifications of this procedure. Which of them give the same result as the original algorithm and which cause some problems? Match the modifications with their effects.

Match the items from left and right columns

Replace

(a, b)

with

(a + b, b)

Replace

(a, b)

with

(a - b, b)

Replace

(a, b)

with

(\lfloor a / b \rfloor, b)

Algorithm successfully computes

\gcd(a, b)

Algorithm never terminates

Algorithm terminates, but returns incorrect answer

___

Create a free account to access the full topic