A ring that is not a Euclidean domain

You might find enlightening the following sketched proof that $\rm\: \mathbb Z[w],\ w = (1 + \sqrt{-19})/2\ $ is a non-Euclidean PID -- based on a sketch by the eminent number theorist Hendrik W. Lenstra.

Note that the proof in Dummit & Foote uses the Dedekind-Hasse criterion to prove it is a PID, and the universal side divisor criterion to prove it is not Euclidean is probably the simplest known. The so-called universal side divisor 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\ a\ :\ m, n \in \mathbb Z\} = \{m + n\ \bar a\ :\ 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 nonreal 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 $\rm\,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$?

What a coincidence, this was a recent homework problem for me as well. Here's an additional hint: Show that $X^2 + X + 5$ does not split over $\mathbb{F}_2$ or $\mathbb{F}_3$. Deduce a contradiction to the minimality of the degree of $x$.

You don't need to know what the degree function looks like to choose $x$: you already chose it when you said "$x$ an element of minimal degree." (By the well-ordering principle, the set of degrees of nonzero, non-unital elements has a least element.)