Have I found an example of norm-Euclidean failure in $\mathbb Z [\sqrt{14}]$?

Based on the proof that $\mathcal O_{\mathbb Q (\sqrt{-19})}$ is not Euclidean because it lacks universal side divisors, I have convinced myself that $\mathbb Z [\sqrt{14}]$ is Euclidean because it has as universal side divisors numbers with a norm of $2$, e.g., $4 + \sqrt{14}$ (though I have not proved this rigorously). Clearly an example of norm-Euclidean failure must involve numbers with odd norms.

I've been looking at $\gcd(3, 7 + 2 \sqrt{14})$. There is a question that's coming up as "similar" that gives $\gcd(3, 3 + \sqrt{14})$ as a possible example of norm-Euclidean failure (for all I know this question might wind up being closed as a duplicate of that one). I have done calculations with both pairs, and I have found (unless I've made errors), that in $3 = q(7 + 2 \sqrt{14}) + r$ results in larger $|N(r)|$ than $3 = q(3 + \sqrt{14}) + r$.

But even if I have made no mistakes of arithmetic, this still does not prove either of these examples leads to norm-Euclidean failure.

July 27, 2016: Just so that hopefully no one can say I have undefined terms: by "an example of norm-Euclidean failure" in this domain I mean a pair of numbers $a, b$ in this domain such that it is impossible to find suitable numbers $q, r$ in this domain to satisfy $a = qb + r$ with $|N(a)| > |N(b)|$ and $|N(b)| > |N(r)|$.

Solution 1:

Although $\mathbb{Z}[\sqrt{14}]$ is not norm-Euclidean, you haven't proved it yet. At least, you can successfully get through one step of the Euclidean algorithm:

$$3 = (7+2\sqrt{14})(-2+\sqrt{14}) + (-11 - 3\sqrt{14}),$$

and the absolute value of the norm of $-11 - 3\sqrt{14}$ is $5$, which is less than the absolute value of the norm of $7+2\sqrt{14}$, which is 7.

ADDED: Mr. Brooks: $(3,3+\sqrt{14})$ certainly does not work. In fact, you can write $$3 = (3 + \sqrt{14})(-4) + (15 + 4\sqrt{14})$$ and note that $15 + 4\sqrt{14}$ is a unit so we've proven $3$ and $3+\sqrt{14}$ are relatively prime.

By the way, here is the trick to use the norm to carry out a Euclidean algorithm:

Goal: Given $a$ and $b$ in the ring of integers, find $q$ in the ring of integers such that $$a = bq + r$$ and $N(r) < N(b)$.

Strategy: Take the quotient $a/b$, which is in the number field, and try to find some integral $q$ such that $N(a/b -q) < 1$. Then set $r = a - bq$ and observe that $$N(r) = N(a - bq) = N(a/b - q)N(b) < N(b).$$

In fact, this leads to a general computational method for trying to prove a number ring is a norm-Euclidean domain: Given a field $K$ and ring of integers $\mathcal{O}$, try to prove that:

For all $x \in K$, there exists $y \in \mathcal{O}$ such that $N(x-y) < 1$.

This gives a geometric approach to the problem.

There are several nice papers by J.P. Cerri which discuss norm-Euclidean domains. I really recommend them if you are interested in this subject (in addition of course to the survey papers by Lenstra and by Lemmermeyer).

PROOF that $\mathbb{Z}[\sqrt{14}]$ is not a norm-Euclidean domain: I'm not sure what the standard proof is, but here is one that works:

Consider $x = (1+\sqrt{14})/2$. We want to show that for any $y \in \mathbb{Z}[\sqrt{14}]$ that $N(x+y) > 1$. Write $y = a + b\sqrt{14}$, with $a$ and $b$ integers. Then suppose $$N(x+y) = \left|\left(a+\frac12\right)^2 - 14\left(b+\frac12\right)^2\right| = \left|a^2 + a - 14b^2 - 14b -\frac{13}{4}\right| < 1.$$ Since $a$ and $b$ are integers, the only possibilities are $$a^2 + a - 14b^2 - 14b = 3 \text{ or } 4.$$ We can rule out $3$ because the left hand side is always even. To rule out 4, we observe that $a^2 + a$ can only equal 0, 2, 6 or 12 modulo 14, and in particular never equals 4 modulo 14. So we have a contradiction, proving that $\mathbb{Z}[\sqrt{14}]$ is not norm-Euclidean.

There is another proof at PlanetMath.