Euclidean domain $\mathbb{Z}[\sqrt{d}]$ [duplicate]

Solution 1:

As it turns out, that's actually a highly non-trivial question. I presume you're aware that every Euclidean domain is a UFD. It is also useful, however, to recall the definition of an integrally closed domain. That is, an integral domain $R$ with field of fractions $K$ is considered integrally closed if for any monic polynomial $p(x) = x^n + a_{n-1}x^{n-1} + \ldots + a_0\in R[x]$, if $p$ has a root $\alpha\in K$, then $\alpha\in R$. It can be shown that any UFD is an integrally closed domain, and that $\mathbb{Z}[\sqrt{d}]$ will never be integrally closed for $d$ not square-free.

Secondly, if $d$ is square-free, then since not being integrally closed is an obstruction to being a UFD (which is a necessary for being an ED), we will often extend $\mathbb{Z}[\sqrt{d}]$ into the subring of its fraction field $\mathbb{Q}(\sqrt{d})$ which contains precisely the solutions to monic polynomials in $\mathbb{Z}[\sqrt{d}]$, which is in fact a ring, and we will call this ring $\mathcal{O}_{\mathbb{Q}(\sqrt{d})}$. It is a theorem in algebraic number theory that for square-free nonzero integers $d$, $$\mathcal{O}_{\mathbb{Q}(\sqrt{d})} = \begin{cases} \mathbb{Z}[\sqrt{d}] & \mathrm{if\ } d\equiv 2,3\mod 4 \\ \mathbb{Z}\left[\frac{1+\sqrt{d}}{2}\right] & \mathrm{if\ } d\equiv 1\mod 4 \end{cases}$$ which tells us that for $\mathbb{Z}[\sqrt{d}]$ to be a Euclidean domain, we must have that $d\equiv 2,3\mod 4$.

Here is where we arrive at our next complication: algebraic number theory provides us with a natural norm $N(a+b\sqrt{d}) = a^2 - db^2$ which is multiplicative and takes elements of $\mathcal{O}_{\mathbb{Q}(\sqrt{d})}$ to integers, as can be checked. A ring which is Euclidean under this norm is said to be norm-Euclidean. There do exist rings which are Euclidean but not norm-Euclidean, such as $$\mathbb{Z}\left[\frac{1+\sqrt{69}}{2}\right]$$ but to my knowledge, these types of rings are not fully understood. We do, however, fully understand which quadratic rings are norm-Euclidean. In fact $\mathcal{O}_{\mathbb{Q}(\sqrt{d})}$ is norm-Euclidean if and only if $$d = -11, -7, -3, -2, -1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, \mathrm{\ or\ }73$$ and so, $\mathbb{Z}[\sqrt{d}]$ is norm-Euclidean if and only if $$d = -2, -1, 2, 3, 6, 7, 11, \mathrm{\ or\ }19.$$ I actually don't know if there are any Euclidean domains that are not norm-Euclidean of the form $\mathbb{Z}[\sqrt{d}]$. My suspicion is that there are not, though it is really way beyond my abilities to prove this.

Solution 2:

I just want to fill in a detail that was hinted at in Monstrous Moonshine's answer, which is too long for a comment.

If $d \equiv 1 \pmod 4$, then $\mathbb Z[\sqrt d]$ is certainly not an Euclidean domain. It suffices to try $\gcd(2, 1 + \sqrt d)$. Clearly both numbers are of even norm, and the latter has a norm with absolute value larger than the former, which suggests the former ought to be a divisor of the latter.

But $$\frac{1 + \sqrt d}{2} \not\in \mathbb Z[\sqrt d].$$ Worse, $1 + \sqrt d$ is probably irreducible, which would mean this domain does not have unique factorization.

However, $$N\left(\frac{1 + \sqrt d}{2}\right) = \left(\frac{1}{2}\right)^2 - \left(\frac{\sqrt d}{2}\right)^2 = \frac{1}{4} - \frac{d}{4} = \frac{1 - d}{4},$$ which is an integer because $d \equiv 1 \pmod 4$, so this number that does not look like an algebraic integer is in fact an algebraic integer.

So $\mathbb Z[\sqrt d]$ is not a "complete" domain of algebraic integers. "Lacks integral closure," is the technical term, I believe. If we broaden our view to this "larger" domain, which we can notate $\mathcal O_{\mathbb Q(\sqrt d)}$, then to solve $\gcd(2, 1 + \sqrt d)$ with $1 + \sqrt d = 2q + r$ so that $-4 < N(r) < 4$, we simply set $$q = \frac{1 + \sqrt d}{2}$$ and $r = 0$. Of course this does not guarantee that every pair of numbers in $\mathcal O_{\mathbb Q(\sqrt d)}$ can have its GCD resolved by the Euclidean algorithm with some Euclidean function, let alone the norm function specifically.

A concrete example: $\mathbb Z[\sqrt{21}]$. Then 2 has a norm of 4, and $1 + \sqrt{21}$ has a norm of $-20$, which in absolute value is greater than 4. We see that $$\frac{1 + \sqrt{21}}{2}$$ is an algebraic integer having a minimal polynomial of $x^2 - x - 5$ and a norm of $-5$, and that's clearly a divisor of $-20$.