What other forms can Euclidean failure take?

Solution 1:

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.