So what *is* the Euclidean function for $\mathcal{O}_{\mathbb{Q}(\sqrt{69})}$?

It's my understanding that $\mathcal{O}_{\mathbb{Q}(\sqrt{69})}$ is UFD, PID, and Euclidean, but not norm-Euclidean.

If it were norm-Euclidean, there would be a solution to $28 = q \left(\frac{5}{2} + \frac{\sqrt{69}}{2}\right) + r$ with $q \neq 0$ and $abs(N(r)) < 11$.

Now I get the feeling I'd have infinitely many values of $q$ to check, so instead I'll check all the suitable values for $r$ and see if there is a case in which $28 - r$ or $28 + r$ has a norm divisible by $11$.

• $1$ gives us $27$ and $29$
• $\left(\pm\frac{9}{2} \pm \frac{\sqrt{69}}{2}\right)$ gives us $\left(\pm\frac{47}{2} \pm \frac{\sqrt{69}}{2}\right)$, $\left(\pm\frac{65}{2} \pm \frac{\sqrt{69}}{2}\right)$
• $2$ gives us $26$ and $30$
• $\pm 8 \pm \sqrt{69}$ gives us $\pm 20 \pm \sqrt{69}$, $\pm 36 \pm \sqrt{69}$
• $3$ gives us $25$ and $31$
• $\left(\pm\frac{75}{2} \pm \frac{\sqrt{69}}{2}\right)$ gives us, you get the idea

But now I get this sinking feeling that maybe I do have infinitely many more values of $r$ to check, and that maybe one of those does lead to a suitable $r$...

Regardless of that, it seems to me like trying to implement the Euclidean algorithm with the absolute value of the norm function in this domain is quite futile. So does anyone know what the Euclidean function is for this domain? Is there more than one such function?

And for a real ring that is Euclidean for the absolute value of the norm, like, say, $\mathcal{O}_{\mathbb{Q}(\sqrt{73})}$, how do you more effectively find the appropriate values of $q$ and $r$? In $\mathcal{O}_{\mathbb{Q}(\sqrt{69})}$, I tried division: $$\frac{28}{\left(\frac{5}{2} + \frac{\sqrt{69}}{2}\right)} = \left(\frac{-70}{11} + \frac{14 \sqrt{69}}{11}\right)$$ but couldn't figure out how to round that to a suitable algebraic integer.

Given a number $p = \frac{a}{2} + \frac{b \sqrt{69}}{2}$ which is prime in $\mathcal{O}_{\mathbb{Q}(\sqrt{69})}$, define the function $$f(p) = |\frac{a^2}{4} - \frac{69b^2}{4}| + 3\delta_{23}^{|N(p)|},$$ where $\delta_i^j$ is the infamous Kronecker delta function.

If $n = 0$ then $f(n) = 0$, and if $n$ is a unit, $f(n) = 1$. The function is multiplicative, so for all other numbers in $\mathcal{O}_{\mathbb{Q}(\sqrt{69})}$, it is a simple matter of finding the prime factors, multiplying their norms (making sure to change $-23$ or 23 to 26 as needed) and taking the absolute value of that.

But all this does is put an extra adjustment on the norm function: if $|N(p)| = 23$, then $f(p) = 26$. This adjusted norm function is a suitable Euclidean function for $\mathcal{O}_{\mathbb{Q}(\sqrt{69})}$.

I took this from p. 41 of Bernhard Lutzmann's thesis Quadratic Number Fields that are Euclidean but not Norm-Euclidean for Universität Wien (he wrote it in English, apparently, but for some people it might as well be in Greek). Lutzmann has this annoying insistence on expressing numbers in this ring in the form $a + b \alpha$ where $\alpha = \frac{1}{2} + \frac{\sqrt{69}}{2}$, which does little besides add a layer of complication to the task of computing norms.

On the next page of his Diplomarbeit, he reiterates $\mathcal{O}_{\mathbb{Q}(\sqrt{69})}$ is not norm-Euclidean and argues that the absolute value of the norm function is unsuitable as the Euclidean function but does not produce an actual pair of numbers to demonstrate this, which I consider important because you have put some effort into finding such a pair of numbers. But I doubt I could find that pair any time soon.

EDIT: In his answer, Marco Flores links a free copy of Clark's paper, from which I was able to find this: $\gcd\left(\frac{23}{2} + \frac{3 \sqrt{69}}{2}, 18 + 2 \sqrt{69}\right)$. Note that $(18 + 2 \sqrt{69}) - \left(\frac{23}{2} + \frac{3 \sqrt{69}}{2}\right) = \frac{13}{2} + \frac{\sqrt{69}}{2}$ and $N\left(\frac{13}{2} + \frac{\sqrt{69}}{2}\right) = 25$. Since $25 > 23$, an implementation of the Euclidean GCD algorithm using the absolute value of the norm function could get stuck on an infinite loop. But with the adjusted function, we'd get $25 < 26$ and the algorithm can move on and come to the conclusion that the two numbers are coprime.

As suggested in the comments, the norm function needs indeed very slight adjustments.

Define $ \phi(\pi) = \left\{ \begin{array}{ll} N(\pi) & \mbox{if } \pi \neq 10+3\alpha \\ 23 & \mbox{if } \pi = 10+3\alpha \end{array} \right. $

where $\alpha=\frac{1+\sqrt{69}}{2}$ and $N$ denotes the absolute value of the norm.

$\phi$ is an Euclidean function for $\mathcal{O}_{\mathbb{Q}(\sqrt{69})}$. For the proof, check David Clark's paper.