もう少し簡単にして、これでも動きます：

gcd[x_, y_] :=
Module[{x0 = x, y0 = y}, While[y0 > 0, {x0, y0} = {y0, Mod[x0, y0]}];
x0]