# 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?

• I think your example worked out so nicely because the norm of $7$ and the norm of $1+\sqrt{5}$ is $49$ and $6$ which are relatively prime in $\mathbb Z$. More generally, I wonder if having $\alpha,\beta\in O_K$ such that Nm$(\alpha)$ and Nm$(\beta)$ are relatively prime in the integers will guarantee that the Euclidean procedure will work – RKD Oct 21 '17 at 21:45
• @Ravi It does not, but I like your thinking. Try $\gcd(2, 1 + \sqrt{-6})$. Then $Nm(2) = 4$ and $Nm(1 + \sqrt{-6}) = 7$. But $$1 + \sqrt{-6} = 2 + (-1 + \sqrt{-6}),$$ $$1 + \sqrt{-6} = (2 + 2 \sqrt{-6}) + (-1 - \sqrt{-6})$$ and $$1 + \sqrt{-6} = 2 \sqrt{-6} + (1 - \sqrt{-6}).$$ On second thought, did you mean to limit it to $\mathbb Z[\sqrt{-5}]$? Can't think of an example for that one at the moment. – Robert Soupe Oct 22 '17 at 1:46

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.