What other forms can Euclidean failure take? 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?
 A: Starting from the "snag" given in the OP and unrolling the Euclidean algorithm backwards, one can easily construct a sequence continuing long before hitting a snag. Formally, we construct a sequence $(w_n)_{n\geq 1}$, such that $w_1=2,w_2=1+\sqrt{-5}$ (the initial "snag"), $\frac{w_n}{w_{n+1}}$ rounds to zero (more precisely, $\frac{w_n}{w_{n+1}}=x_n+y_n\sqrt{-5}$ with $|x_n| \leq \frac{1}{3}, |y_n| \leq \frac{1}{3}$), and $\frac{w_{n+1}}{w_{n}}$ rounds to three (more precisely, $\frac{w_n}{w_{n+1}}=3+a_n+b_n\sqrt{-5}$ with $|a_n| \leq \frac{1}{3}, |b_n| \leq \frac{1}{3}$). It turns out that putting $w_{n+2}=3w_{n+1}+w_n$ works.
Here is an example, for $n=5$ :
We start with $w_5=53+33\sqrt{-5}$ and $w_4=16+10\sqrt{-5}$. Then $N(w_5)=8254 \gt 756=N(w_4)$, so we compute 
$$ \frac{w_5}{w_4} = 3+ \frac{115}{378}-\frac{1}{378}\sqrt{-5} \approx 3$$
The next value in the algorithm is therefore $w_3=w_5-3w_4=5+3\sqrt{-5}$. We compute 
$$ \frac{w_4}{w_3} = 3+ \frac{2}{7}+\frac{1}{35}\sqrt{-5} \approx 3$$
The next value in the algorithm is therefore $w_2=w_4-3w_3=1+\sqrt{-5}$. We compute 
$$ \frac{w_3}{w_2} = 3+ \frac{1}{3}-\frac{1}{3}\sqrt{-5} \approx 3$$
The next value in the algorithm is therefore $w_1=w_3-3w_2$, and $(w_2,w_1)=(1+\sqrt{-5},2)$ is the snag described in the OP.
