Euclid's algorithm?

Question

Consider the following procedure that purportedly finds the greatest common divisor of x and y, x>y.

FindGCD(x,y)
--If y|x return y
--Else return FindGCD(x, x mod y)

Is this procedure correct? if so, is it significantly faster or slower than Euclid's algorithm? Of not correct, why not?

Answer 1

This procedure is not correct. For consider GCD(24, 15). Since 24 = 2³*3 and 15 = 3*5, GCD(24, 15) = 3. However, running this procedure:

FindGCD(24, 15) = FindGCD(24, 9) = FindGCD(24, 6) = 6.

So this procedure is not correct.