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?

  • 4
    $\begingroup$ 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 $\endgroup$ – RKD Oct 21 '17 at 21:45
  • 4
    $\begingroup$ @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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.