Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\alpha = \frac{1+\sqrt{-19}}{2}$. Let $A = \mathbb Z[\alpha]$. Let's assume that we know that its invertibles are $\{1,-1\}$. During an exercise we proved that:

Lemma: If $(D,g)$ is a Euclidean domain such that its invertibles are $\{1,-1\}$, and $x$ is an element of minimal degree among the elements that are not invertible, then $D/(x)$ is isomorphic to $\mathbb Z/2\mathbb Z$ or $\mathbb Z/3\mathbb Z$.

Now the exercise asks:

Prove that $A$ is not a Euclidean Domain.

Everything hints to an argument by contradiction: let $(A, d)$ be a ED and $x$ an element of minimal degree among the non invertibles we'd like to show that $A/(x)$ is not isomorphic to $\mathbb Z/2\mathbb Z$ or $\mathbb Z/3\mathbb Z$.

How do we do that? My problem is that, since I don't know what this degree function looks like, I don't know how to choose this $x$!

I know that the elements of $A/(x)$ are of the form $a+(x)$, with $a$ of degree less than $x$ or zero. By minimality of $x$ this means that $a\in \{0, 1, -1\}$. Now I'm lost: how do we derive a contradiction from this?

share|cite|improve this question
up vote 8 down vote accepted

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$.

share|cite|improve this answer
$X^2-X+5$ doesn't split in $\mathbb F_{2}[X]$ or $\mathbb F_{3}[X]$ because it has no roots in those fields. But it does split in $A[X]$, thus in $A/(x)[X]$. Contradiction! I hope :) – Jacopo Notarstefano Feb 26 '11 at 15:56
@Jacopo: Yes, something like that. Essentially what happens is that you are forced to conclude that $A/(x)$ is the trivial ring, so $x$ must be a unit, but we already excluded all the units. – Zhen Lin Feb 26 '11 at 16:19

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$?

share|cite|improve this answer
The link to Dedekind-Hasse criterion points to this answer and should be corrected. +1 for an otherwise great answer. – Paramanand Singh Jul 5 at 16:02
@ParamanandSingh The link has been updated, thanks. – Bill Dubuque Jul 5 at 16:05

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.)

share|cite|improve this answer
I guess I should have phrased my question better. I do understand that this $x$, given a degree function, exists. I'll try to edit my question to better reflect what I was trying to say. – Jacopo Notarstefano Feb 26 '11 at 14:22
@Jacopo: oh. That's a completely different question. Then in fact Zhen Lin gave you the correct hint. – Qiaochu Yuan Feb 26 '11 at 15:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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