Ring of integers is a PID but not a Euclidean domain I have noticed that to prove fields like $\mathbb{Q}(i)$ and $\mathbb{Q}(e^{\frac{2\pi i}{3}})$ have class number one, we show they are Euclidean domains by tessellating the complex plane with the points $a+bv : a, b \in \mathbb{Z}$, where $1, v$ is an integral basis.  Then any $c +dv$ in the field has distance $\leq 1$ from some lattice point.  On the other hand a similar geometric argument fails with the field $\mathbb{Q}(\sqrt{-5})$, which does not have class number one.    
Any ring of integers of a finite extension of $\mathbb{Q}$ is a Dedekind domain, hence a PID if and only if a UFD.  But can such a ring be a PID but fail to be a Euclidean domain?
 A: Here's what I think is a nice way to find a few PIDs that aren't Euclidean. It's not quite elementary, but if you know a bit about number fields I think it's a lot easier and nicer than the normal drudge. 
Let $K=\mathbb{Q}(\sqrt{-d})$ for $d>3$ squarefree, with ring of integers $\mathcal{O}_K$. Then the only units in $\mathcal{O}_K$ are $\pm1$.
Suppose $\mathcal{O}_K$ is Euclidean with Euclidean function $\varphi$. Then take $x \in \mathcal{O}_K\setminus\{0,\pm1\}$ with $\varphi(x)$ minimal. By definition, any element of $\mathcal{O}_K$ can be written in the form $px+r$ where $\varphi(r) < \varphi(x)$, so it must be that $r \in \{0,\pm1\}$, i.e. $|\mathcal{O}_K/(x)|$ is $2$ or $3$. In other words $\mathcal{O}_K$ has a principal ideal of norm $2$ or $3$.
So now we know that if $K = \mathbb{Q}(\sqrt{-d})$ has class number one, where $d>3$ is squarefree*, $K$ is a non-Euclidean PID if there are no elements in $\mathcal{O}_K$ of norm $\pm2$ or $\pm3$. As $K$ is a PID (and degree $2$ over $\mathbb{Q}$), this is equivalent to saying that $2$ and $3$ are inert. To find some examples then:
If $d = 3\pmod{4}$, $\mathcal{O}_K = \mathbb{Z}[\frac{1+\sqrt{-d}}{2}]$, the minimal polynomial of $\frac{1+\sqrt{-d}}{2}$ over $\mathbb{Q}$ is $f_d(X)=X^2-X+\frac{1+d}{4}$. Applying Dedekind's criterion gives that $d$ works provided that $f_d(X)$ is irreducible $\pmod{2}$ and $\pmod{3}$. This then gives that $d = 19$ works (which is the usual example), but also shows that $d = 43,67$ or $163$ work as well (I think!).
*It can be shown that this implies $d \in \{1,2,3,7,11,19,43,67,163\}$
A: $\Bbb{Z}[\frac{1+\sqrt{-19}}{2}]$ is not a E.D..
Supose that $R=\Bbb{Z}[\frac{1+\sqrt{-19}}{2}]$ is a E.D..
Let $N(\cdot)$ be the Euclidean norm.
Recall that the set of all unit in $R$ is $\{\pm 1\}$.
Take an element $a\notin \{0, \pm 1\}$ such that $N(a)$ is minimal.
For any $b\in R$,
we have $b=aq+r$,
where $r=0$ or $N(r)<N(a)$.
By the minimality of $N(a)$,
we have $r\in \{0, \pm 1\}$.
Thus, $R/\langle a\rangle\cong \Bbb{Z}_2$ or $\Bbb{Z}_3$.
On the other hand,
the polynomial $x^2+x+5$ has root in $R$
because $x^2+x+5=[x-(-\frac{1+\sqrt{-19}}{2})][x-(-1+\frac{1+\sqrt{-19}}{2})]$.
So $x^2+x+5$ has root in $R/\langle a\rangle$.
But $x^2+x+5$ has no root in $\Bbb{Z}_2$ nor in $\Bbb{Z}_3$.
Hence, $R/\langle a\rangle$ can't be isomorphic to $\Bbb{Z}_2$ nor $\Bbb{Z}_3$.
$\Bbb{Z}[\frac{1+\sqrt{-19}}{2}]$ is a P.I.D. (See Artin's Algebra ch.13)
Since $-19\equiv 1\pmod{4}$,
we compute $\mu=\sqrt{\frac{|-19|}{2}}\approx 2.52$
and the prime integers don't exceed $\mu$ is $2$.
Note that $x^2-x+\frac{1-(-19)}{4}=x^2-x+5$ is irreducible in $\Bbb{F}_2[x]$.
Hence, $\langle 2\rangle$ is a prime ideal in $\Bbb{Z}[\frac{1+\sqrt{-19}}{2}]$.
Since $\langle 2\rangle$ is principal,
the ideal class of $\langle 2\rangle$ in the class group is the identity.
Thus,
the ideal class group is trivial and $\Bbb{Z}[\frac{1+\sqrt{-19}}{2}]$ is a P.I.D..
Lemma 1.
The ideal class group $\mathcal{C}$ is generated by the classes of prime ideal $P$ whose norms are prime integers $p\leq \mu$
Lemma 2.
If $d\equiv 1\pmod{4}$,
then $\langle p\rangle$ is a prime ideal in $\Bbb{Z}[\frac{1+\sqrt{d}}{2}]$ if and only if
the polynomial $x^2-x+\frac{1-d}{4}$ is irreducible in $\Bbb{F}_p[x]$.
$$\begin{array}{rcl}
\Bbb{Z}[x] & \stackrel{\langle p\rangle}{\longrightarrow} & \Bbb{F}_p[x] \\
/\langle x^2-x+\frac{1-d}{4}\rangle \downarrow& & \downarrow /\langle x^2-x+\frac{1-d}{4}\rangle \\
\Bbb{Z}[\frac{1+\sqrt{d}}{2}] & \stackrel{\langle p\rangle}{\longrightarrow} & R'
\end{array}
$$
A: Yes, below is a sketch a proof that $\rm\: \mathbb Z[w],\ w = (1 + \sqrt{-19})/2\ $ is a non-Euclidean PID, based on remarks of Hendrik W. Lenstra.
The standard proof usually employs the Dedekind-Hasse criterion
to prove it is a PID, and the universal side divisor criterion
to prove it is not Euclidean, e.g. see Dummit and Foote.
The latter criterion is essentially a
special case of research of Lenstra, Motzkin, Samuel, Williams 
et al. that applies in much wider generality to Euclidean domains. 
You can obtain a deeper understanding of Euclidean domains from
the excellent surveys by Lenstra in Mathematical Intelligencer
1979/1980 (Euclidean Number Fields 1,2,3) and Lemmermeyer's superb survey The Euclidean algorithm in algebraic number fields. Below is said sketched proof of Lenstra, excerpted from George Bergman's web page.

Let $\rm\:w\:$ denote the complex number $\rm\ (1 + \sqrt{-19})/2\:,\:$ and $\rm\:R\:$ the ring $\rm\: Z[w]\:.$ 
We shall show that $\rm\:R\:$ is a principal ideal domain, but not a Euclidean
ring. This is Exercise III.3.8 of Hungerford's Algebra (2nd edition),
but no hints are given there; the proof outlined here was sketched for
me (Bergman) by H. W. Lenstra, Jr.
$(1)\ $ Verify that $\rm\  w^2\! - w + 5 = 0,\:$ that  $\rm\ R = \{m + n\ w\ :\ m, n \in \mathbb Z\} = \{m + n\ \bar w\ :\ m, n \in \mathbb Z\},\:$ where the bar denotes complex conjugation, and that the map  $\rm\ x \to |x|^2 = x \bar x\ $  is nonnegative integer-valued 
and respects multiplication.
$(2)\ $ Deduce that $\rm\ |x|^2 = 1\ $  for all units of $\rm\:R\:,\:$ and using a lower bound on the absolute value of the imaginary part of any noneal member of $\rm\:R\:,\:$ conclude that the only units of $\rm\:R\:$ are $\pm 1\:.$
$(3)\ $ Assuming $\rm\:R\:$ has a Euclidean function $\rm\:h,\:$ let $\rm\:x\ne 0\:$ be a nonunit of $\rm\,R\,$ minimizing $\rm\: h(x).\:$  Show that $\rm\:R/xR\:$ consists of the images in this ring of $\:0\:$ and the units of $\rm\:R\:,\:$ hence has cardinality at most $3$. What nonzero rings are there of such cardinalities?  Show  $\rm\ w^2 - w + 5 = 0 \ $ has no solution in any of these rings, and deduce a contradiction, showing that R is not Euclidean.
We shall now show that $\rm\:R\:$ is a principal ideal domain. To do this, let
$\rm\:I\:$ be any nonzero ideal of $\rm\:R\:,\:$ and  $\rm\:x\:$  a nonzero element of $\rm\:I\:$ of least absolute value, i.e., minimizing the integer $\rm\ x \bar x\:.\:$ We shall prove $\rm\ I = x\:R\:.\:$ (Thus, we are using the function $\rm\ x \to x \bar x\ $  as a substitute for a Euclidean function, even though it doesn't enjoy all such properties.)
For convenience, let us "normalize" our problem by taking  $\rm\ J = x^{-1}\ I\:.\:$ Thus, $\rm\:J\:$ is an $\rm\:R$-submodule of $\:\mathbb C\:,\:$ containing $\rm\:R\:$ and having no nonzero element of absolute value $< 1\:.\:$ We shall show from these properties that $\rm\: J - R = \emptyset\:,\:$ i.e., that $\rm\ J = R\:.$
$(4)\ $ Show that any element of $\rm\:J\:$ that has distance less than $1$ from some element of $\rm\:R\:$ must belong to $\rm\:R\:.\:$  Deduce that in any element of  $\rm\ J - R\:,\:$ the imaginary part must differ from any integral multiple of  $\:\sqrt{19}/2\:$  by at least $\:\sqrt{3}/2\:.\:$ (Suggestion: draw a picture showing the set of complex numbers which the preceding observation excludes. However, unless you are told the contrary, this picture does not replace a proof; it is merely to help you find a proof.)
$(5)\ $ Deduce that if $\rm\: J - R\:$  is nonempty, it must contain an element  $\rm\:y\:$  with imaginary part in the range $\rm\ [\sqrt{3}/2,\ \sqrt{19}/2 - \sqrt{3}/2]\:,\:$ and real part in the range $\rm\: (-1/2,\ 1/2]\:.$
$(6)\ $ Show that for such a $\rm\: y\:,\:$ the element $\rm\: 2\:y\:$  will have imaginary part too close to  $\:\sqrt{19}/2\:$  to lie in $\rm\: J - R\:.\:$  Deduce that  $\rm\ y = w/2\ $  or  $\rm- \bar w/2\:,\:$ and hence that $\rm\ w\ \bar w/2\ \in J\:.$
$(7)\ $ Compute  $\rm\: w\ \bar w/2\:,\:$ and obtain a contradiction. Conclude that $\rm\:R\:$ is a principal ideal domain.
$(8)\ $ What goes wrong with these arguments if we replace $19$ throughout by $17$?
By $23$?
