I know that $\mathbb{Z}[\sqrt{-5}]$ is not a Euclidean domain. However, I'm still interested in trying to see how far the Euclidean algorithm can get.
With some numbers, it can get all the way to the result, e.g., $\gcd(7, 1 + \sqrt{5})$, we have $$\frac{7}{1 + \sqrt{5}} = \frac{7}{6} - \frac{7 \sqrt{-5}}{6},$$ which neatly rounds down to $1 - \sqrt{-5}$ and then we readily see that $7 = (1 - \sqrt{5})(1 + \sqrt{5}) + 1$ and therefore the two numbers are coprime.
Obviously, the algorithm won't get very far for something like $\gcd(2, 1 + \sqrt{5})$, but then I was wondering: is it possible for the algorithm to actually get very far along and then hit a snag? I tried $\gcd(4, 2 + 2 \sqrt{-5})$, but there the obstacle is also immediately hit.
Which makes me think that if it's possible to find a remainder of suitable norm, it's also possible for the algorithm to go all the way. Is this correct?