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

• From the MathSciNet review of David Clark's paper that $\mathbf Z[(1+\sqrt{69})/2]$ is Euclidean despite not being norm-Euclidean: "it can be shown [...] that every completely multiplicative function from [...] $\mathbf Z[(1+\sqrt{69})/2]$ to the positive real numbers which sends the prime elements above 23 to a value larger than 25 and which agrees with the absolute norm at all other primes defines a Euclidean algorithm for this ring." So the problem is due in some sense entirely to the primes lying over 23, which up to unit multiples are $10 + 3(1\pm\sqrt{69})/2$. So focus attention there. – KCd Jan 3 '15 at 23:52
• @Kcdilla, in our paper, Pete recommends Lemmermeyer 1995 for what I suspect is this material. Similar, anyway. Well, Franz, Proposition 4.10 anyway. – Will Jagy Jan 4 '15 at 1:17
• @KCd By "primes lying over 23," do you mean "primes greater than 23"? Then it should actually be possible to put 11's divisor and 28 through the Euclidean algorithm with good ol' norm. Then $q = \left(-\frac{9}{2} + \frac{3\sqrt{69}}{2}\right)$ and $r = -\left(\frac{25}{2} + \frac{3\sqrt{69}}{2}\right)$. I think Albert could have found this on his own but for whatever reason, he forgot about the other units. – Robert Soupe Jan 4 '15 at 2:02
• @RobertSoupe: I meant "over 23" in the sense of algebraic number theory, i.e., the primes of that ring that divide 23. – KCd Jan 4 '15 at 2:23
• @RobertSoupe: I meant what I wrote: $(23\pm 3\sqrt{69})/2$ if you want to simplify it. If you prefer $299+36\sqrt{69}$ instead, be my guest. It is not really different from $(23+3\sqrt{69})/2$, as they differ by a unit factor: $299+36\sqrt{69} = u(23+3\sqrt{69})/2$ where $u = (25+3\sqrt{69})/2$ has norm $1$. Concerning your distaste for the term "over", it is not strange: we write diagrams of primes in a ring of integers over prime numbers in the same way a covering space is drawn, with a vertical orientation. It's like saying one field lies "over" another, from how they're usually drawn. – KCd Jan 4 '15 at 3:04

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.

• Thank you very much for that link. I found a Springer link which only showed the first two pages, just before it got to the good part. – Robert Soupe Jan 11 '15 at 3:55
• I had a bit of a quandary here. Robert Soupe does give a pair of numbers for which the second norm adjustment is necessary. But he only did so after Marco Flores posted a free link to David Clark's paper. I've decided to award the bounty to Marco, but I recommend to Albert he accept Robert's answer. – James47 Jan 13 '15 at 21:41