# What is the Euclidean function for $\mathbb{Z}[\sqrt{14}]$?

I've tried a few different pairs of numbers in $\mathbb{Z}[\sqrt{14}]$ and in each case I've been able to find a remainder for which the absolute value of the norm is suitable for the Euclidean algorithm. But the Tooth Fairy tells me that $\mathbb{Z}[\sqrt{14}]$ is not norm-Euclidean. If not the absolute value of the norm, then what is the Euclidean function for $\mathbb{Z}[\sqrt{14}]$? This riddle has me stumped.

• I don't understand why are you convinced that such an Euclidean function exists. Feb 14, 2015 at 22:30

This ring, as well as all the other number rings that were shown to be Euclidean using analytic techniques, are Euclidean with respect to the minimal Euclidean function $$f$$, which in your case is defined as follows.

We set $$f(r) = 0$$ iff $$r = 0$$.

We set $$f(r) = 1$$ iff $$r$$ is a unit, i.e, for elements $$\pm (15+4\sqrt{14})^n$$.

We set $$f(r) = 2$$ for all other elements whose residue classes are represented by elements with $$f(r) \le 1$$. This includes elements of norm $$2$$ but also (probably) infinitely many prime elements that have the fundamental unit as a primitive root.

We set $$f(r) = 3$$ for all other elements whose residue classes are represented by elements with $$f(r) \le 2$$.

Continue this process indefinitely. It can be shown (but only with analytic means so far) that $$f$$ is a Euclidean function on $${\mathbb Z}[\sqrt{14}]$$.

It is straightforward to compute $$f(r)$$ for a given element; the difficult problem is showing that every element $$r$$ has a finite value $$f(r)$$.

Edit. Perhaps "straightforward" is too strong a word. Let me compute the value $$f(7+2\sqrt{14})$$ for the element $$\pi = 7+2\sqrt{14}$$ generating the prime ideal of norm $$7$$.

I first claim that $$f(\pi) \ge 3$$. In fact, $$\pi$$ is not a unit, so $$f(\pi) \ge 2$$. Next, $$\varepsilon = 15 + 4 \sqrt{14} \equiv 1 \bmod \pi$$ shows that all units are $$\equiv \pm 1 \bmod \pi$$, so only the residue classes $$0$$ and $$\pm 1$$ are covered by elements with $$f(r) \le 1$$. But this shows that $$f(\pi) \ge 3$$.

Next I claim that $$f(4 + \sqrt{14}) = f(5 + \sqrt{14}) = 2$$. The first element has norm $$2$$, so the claim is trivial. For the second we observe that $$\varepsilon \equiv -5 \bmod (5 + \sqrt{14})$$, and since $$-5$$ is a primitive root modulo $$11$$, all the residue classes of $$5 + \sqrt{14}$$ are represented by units.

For showing that $$f(\pi) \le 3$$ I have to represent the residue classes $$0$$, $$\pm 1$$, $$\pm 2$$ and $$\pm 3$$ modulo $$\pi$$ by elements $$r$$ with $$f(r) \le 2$$. This now follows easily as $$-2 \equiv 5 + \sqrt{14} \bmod \pi$$ and $$-3 \equiv 4 + \sqrt{14} \bmod \pi$$.

• How do you compute $f(r)$ for a given element $r$?
– Mark
Feb 22, 2017 at 18:16

It's not the norm function, that much I can tell you for sure.

From an answer to this question Have I found an example of norm-Euclidean failure in $\mathbb Z [\sqrt{14}]$? I have gleaned a pair of numbers that prevent a successful run of the Euclidean algorithm with the absolute value of the norm as the Euclidean function. And it helps that in a comment to yet another question on this topic the answerer gives a specific pair of numbers.

$$\gcd(2, 1 + \sqrt{14}) = 1$$

Now I will work out the specifics of why that specific result can't be obtained by the norm-Euclidean algorithm.

Since $N(1 + \sqrt{14}) = -13$ and $N(2) = 4$, we need to solve $1 + \sqrt{14} = 2q + r$ so that $-4 < N(r) < 4$.

We already know that 2 and $1 + \sqrt{14}$ are coprime, so $r = 0$ is hardly worth mentioning.

The fundamental unit is $\eta = 15 + 4\sqrt{14}$ (note that $N(\eta) = 1$, not $-1$). If $\eta^n = a + b\sqrt{14}$, then it is obvious that $a$ must be odd and $b$ even. But if $2q = c + d\sqrt{14}$ then both $c$ and $d$ are even, and $r = \eta^n$ will not work because we need $b + d = 1$ (though, for what it's worth, $a + c = 1$ is possible).

Let's try now for $N(r) = 2$, which means that $r = \pm(4 \pm \sqrt{14})^n$. If $r = a + b\sqrt{14}$, then $a$ is always even ($n = 0$ doesn't count because that gives us one of the units, which we've already gone over). But $2q = c + d\sqrt{14}$ has $c$ even, and in this case $a + c = 1$ is impossible.

Since $$\left(\frac{14}{3}\right) = -1,$$ 3 is prime in this domain and $N(x) = \pm 3$ is impossible.

Hence the Euclidean algorithm is stymied by this pair of numbers.

I read somewhere that someone has compiled a lot of empirical evidence suggesting that these difficulties can be overcome by "cheating" in $\mathbb Z[\sqrt{14}, \frac{1}{2}]$.

It's not proven, but it does suggest a possible Euclidean function: if the norm is even, then double it. Then we'd have $\tilde N(2) = 8$, and we'd be able to proceed thus: $1 + \sqrt{14} = 2 \times 2 + (-3 + \sqrt{14})$, then $2 = (-3 + \sqrt{14})(-4 - \sqrt{14}) + (4 + \sqrt{14})$ (this still works even though we have to double the norm of $4 + \sqrt{14}$ to 4), and then finally $-3 + \sqrt{14} = (4 + \sqrt{14})(-11 + 4\sqrt{14}) - \eta$. Obtaining a unit as a remainder confirms the two initial numbers are coprime.

But this does not rule out the possibility that someone could find a pair of numbers that similarly stymies this Euclidean function I'm proposing.

The purpose of this community wiki post is to show that $\mathbb Z[\sqrt{14}]$ is does not fail the first step in Motzkin's construction of a Euclidean algorithm, thereby providing some useful background for the other answers.

Every number of even norm is divisible by $4 + \sqrt{14}$, which has a norm of 2.

If $a + b \sqrt{14}$ has even norm and $a$ and $b$ are both even, we can set $$c = \frac{a}{2}, d = \frac{b}{2}.$$ It doesn't matter if $c + d \sqrt{14}$ is itself divisible by $4 + \sqrt{14}$, because 2 is.

Of course $a + b \sqrt{14}$ can still have even norm if $b$ is odd, provided that $a$ is still even. It's only a tiny bit more complicated to show that such a number is also divisible by $4 + \sqrt{14}$. Set $$c = -7b + 2a, d = 2b - \frac{a}{2}$$ and verify that $(4 + \sqrt{14})(c + d \sqrt{14}) = a + b \sqrt{14}$.

Now suppose that $a + b \sqrt{14}$ has odd norm. This means that $a$ must be odd. But if you increment or decrement $a$ by 1, you have a number of even norm which is therefore divisible by $4 + \sqrt{14}$. This means that $4 + \sqrt{14}$ is a universal side divisor in this domain (not everyone likes that terminology, but it seems to be almost standard).

The presence of a universal side divisor means the second subset in Motzkin's construction is non-empty so that Motzkin's construction does not fail at this level. When the second subset is empty, as for example in $\mathcal O_{\mathbb Q(\sqrt{-19})}$, we can conclude that the ring is not a Euclidean domain. In this case the second subset is non-empty. We cannot conclude that $\mathbb Z[\sqrt{14}]$ is Euclidean, but we know that the technique used to prove domains non-Euclidean by failure of Motzkin's construction does not apply to $\mathbb Z[\sqrt{14}]$. It also gives no guidance as to what the Euclidean function might be.

It should be noted, however, that for many pairs of numbers in $\mathbb Z[\sqrt{14}]$ the absolute value of the norm does properly work as a Euclidean function. For example, using the foregoing, it should be a breeze to find $r = 0$ or 1 for $\gcd(4 + \sqrt{14}, a + b \sqrt{14})$. Certain multiples of $4 + \sqrt{14}$ could be problematic, however, as the other answers will elaborate.

• Please give a reference where it is proved that the presence of a universal side divisor implies the domain is Euclidean, Dec 9, 2017 at 13:20
• @Malcolm Presence of a universal side divisor in a ring together with that ring being a principal ideal domain is enough to prove the domain is Euclidean. This is to be gleaned from any paper that proves the ring of $\mathbb{Q}(\sqrt{-19})$ is not Euclidean; this is gleaned more easily from some papers than others, which holds me back from editing this community wiki answer. Dec 9, 2017 at 22:39
• @Mr.Brooks Reference please. The proof at maths.qmul.ac.uk/~raw/MTH5100/PIDnotED.pdf that $\mathcal O_{\mathbb Q(\sqrt{-19})}$ is not Euclidean makes no mention that somehow or other the presence of a side divisor implies the ring is Euclidean. Certainly Motzkin's original proof that $\mathcal O_{\mathbb Q(\sqrt{-19})}$ is not Euclidean contains no such claim. Neither does Samuel's seminal paper. Dec 9, 2017 at 23:26
• @Malcolm Sounds like something you should add to this community wiki post. I got somewhat more complicated math on my mind today: NFL stats. ;-) Dec 10, 2017 at 17:15
• @Malcolm Thank you very much for your edit. Today I've been dealing with a personal issue I won't burden you with, and I would much rather focus on this than that. Thanks for taking care of this. Dec 12, 2017 at 19:42

The Tooth Fairy is wrong.

This is a classic question. Until semi-recently, the euclidian character of this ring was proved conditionally to the generalized Riemann hypothesis, by Clark (and maybe another guy), but in 2004, Harper gave an unconditional proof. See here.

• If you click where it says "Read article [PDF: 223KB]" it should load in your browser. It's a 16-page paper and I just barely understand the first page, but in my skimming ahead I don't see where it says what the Euclidean function is for this domain. Feb 15, 2015 at 1:42
• First of all, $\mathbf{Z}[\sqrt{14}]$ is not norm euclidian (easy to check), but is euclidian. Now, what is its euclidian fonction (in the sense of Samuel's second definition) ? Look at proposition 4 of the paper (the classic Motzkin's lemma). (The lemma is btw proved in Samuel's book, that you can easily find...) This lemma states that under certain conditions, a ring is euclidian. You should first look at this proof (in Samuel's book for instance) to see how they construct the euclidian function, to get some intuition. Now, Harper proves a variation of Motzkin's lemma to conclude... Feb 15, 2015 at 10:43
• ... so reading carefully the proof of this variation (plus the use of the sieve method) should allow you to construct the euclidian function. I did it a years ago, and it is ok, just follow linearly arguments, and patch. Feb 15, 2015 at 10:44
• Another exposition of the proof is given at thales.doa.fmph.uniba.sk/macaj/skola/atc/LutzmannDipl.pdf but the author writes "we are not able to explicitely write down an Euclidean algorithm". But the author does give a Euclidean algorithm for ${\bf Q}(\sqrt{69})$, which is also Euclidean but not norm-Euclidean. Feb 15, 2015 at 11:50
• Your opening sentence is wrong. The Tooth Fairy did not say that $\mathbb Z[\sqrt{14}]$ was not a Euclidean domain. Feb 18, 2017 at 15:00