For which integer $d$ is the ring $\mathbb{Z}[\sqrt{d}]$ norm-Euclidean?

Here I'm referring to $\mathbb{Z}[\sqrt{d}] = \{a + b\sqrt{d} : a,b \in \mathbb{Z}\}$, not the ring of integers of $\mathbb{Q}[\sqrt{d}]$.

For $d < 0$, it is easy to show that only $d = -1, -2$ suffice; but what about $d>0$?


  • $\begingroup$ The norm-Euclidean quadratic fields are those with $d=2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 73$. OEIS. Which means $\mathbb{Z}[\sqrt{d}]$ for $d=2,3,6,7,11,19,73$, at least, are norm-euclidean. $\endgroup$ – Arturo Magidin Aug 19 '11 at 20:57
  • $\begingroup$ Why are the $d \equiv 1$ left out? Thanks. $\endgroup$ – Isaac Aug 19 '11 at 21:13
  • 2
    $\begingroup$ Because you were asking about $\mathbb{Z}[\sqrt{d}]$; the norm-Euclidean quadratic fields are those for which the ring of integers is norm Euclidean, and if $d\equiv 1\pmod{4}$, then the ring of integers is $\mathbb{Z}[\frac{1+\sqrt{d}}{2}]$. I don't know off-hand whether $\mathbb{Z}[\sqrt{d}]$ is norm-Euclidean if $\mathbb{Z}[\frac{1+\sqrt{d}}{2}]$ is norm-Euclidean in those cases, hence the "at least". $\endgroup$ – Arturo Magidin Aug 19 '11 at 21:19
  • 5
    $\begingroup$ Euclidean domains are integrally closed, so any proper subring of the full ring of integers cannot be Euclidean. $\endgroup$ – Bill Dubuque Aug 19 '11 at 21:50
  • $\begingroup$ ... Oop @Bill D. must have been composing the same...The non-integrally-closed orders cannot be Euclidean at all, because then they'd be PIDs, which is impossible because not-integrally-closed rings cannot be even Dedekind. It's true! :) $\endgroup$ – paul garrett Aug 19 '11 at 21:51

The ring of integers of the real quadratic number field $\rm\:\mathbb Q(\sqrt{d})\:$ is norm-Euclidean iff $\rm\:d = 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 73\:.\:$ For this result and much more of interest see Franz Lemmermeyer's excellent survey The Euclidean Algorithm in Algebraic Number Fields.

Regarding the edited question: since a Euclidean domain is integrally closed, any proper subring of the full ring of integers, being not integrally closed, is not Euclidean. That Euclidean domains are integrally closed is nothing more than the standard simple proof of the Rational Root Test.

  • $\begingroup$ Has anyone exposited the proof of the euclidean real quardatic fields in one place ? $\endgroup$ – Rene Schipperus Sep 1 '14 at 21:16
  • $\begingroup$ The link appears to be dead, however the paper is avaible here. $\endgroup$ – Jarek Kuben Nov 18 '17 at 13:47

Your exact question has already been resolved and is today a simple matter of looking it up in the OEIS and sifting out the numbers of the form $4k + 1$.

$$d = 2, 3, 6, 7, 11 \textrm{ or } 19$$

But it was a long, slow process throughout the 20th century to arrive at this answer, as Ian Stewart and David Tall explain in their excellent book Algebraic Number Theory and Fermat's Last Theorem.

Here I'm referring to $\mathbb{Z}[\sqrt{d}] = \{a + b\sqrt{d} : a, b \in \mathbb{Z}\}$, not the ring of integers of $\mathbb{Q}[\sqrt{d}]$.

Because you said this, it's necessary to sift out the numbers of the form $4k + 1$. Stewart & Tall (and many other authors in other books) show that if a domain is Euclidean then it is a principal ideal domain and a unique factorization domain (the converse doesn't always hold, but that's another story).

So if $d > 5$, $d \equiv 1 \pmod 4$ and $$m = \frac{d - 1}{4},$$ (that's an integer) then $d - 1 = 2^2 m = (-1)(1 - \sqrt d)(1 + \sqrt d)$ represents two distinct factorizations of the same number, which means that $\mathbb Z[\sqrt d]$ is not a unique factorization domain, which in turns means it can't be Euclidean and certainly not norm-Euclidean.

If you had asked about Euclidean in general, you question would be significantly more difficult. The Euclidean function for $\mathcal O_{\mathbb Q(\sqrt{69})}$ was only recently (just a couple of decades ago) discovered: the norm function requires two adjustments and is somewhat frustrating for practical applications.

And it has been proven that $\mathbb Z[\sqrt{14}]$ is Euclidean but not norm-Euclidean, but no one on Math.SE seems to know what the Euclidean function might be (it has been asked).

  • $\begingroup$ Do you have a link to where it's been asked? ​ ​ $\endgroup$ – user57159 Apr 8 '17 at 12:06
  • $\begingroup$ @Ricky Are you asking for a Math.SE link? If I had that, I would have voted to close the question as a duplicate. To my knowledge, Isaac is the only one to ask this question with the stricture $d \not\equiv 1 \pmod 4$. $\endgroup$ – Robert Soupe Apr 8 '17 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.