I'm talking about the ring of algebraic integers of the form $\frac{a}{2} + \frac{b \sqrt{-19}}{2}$, where $a, b \in \mathbb{Z}$.

This ring is said to be a principal ideal domain but not a Euclidean domain to any suitable function.

Since its not norm-Euclidean, it should be possible to find specific numbers $n, b, q, r \in \mathcal{O}_{\mathbb{Q}(\sqrt{-19})}$ such that $n = qb + r$ yet $N(r) > N(b)$. Or would the failure of Euclideanness manifest itself in some other way?

I've looked at a few different books and papers, and alot of them give a concrete example (usually $6$) for $\mathbb{Z}[\sqrt{-5}]$ not being UFD, but no example to show $\mathcal{O}_{\mathbb{Q}(\sqrt{-19})}$ is PID but not Euclidean with respect to some function.

  • 1
    $\begingroup$ See Abstract Algebra by Dummit & Foote, Section $8.1$ & $8.2$ $\endgroup$ – Krish Nov 26 '14 at 22:42
  • $\begingroup$ entering it into library's search box right now... $\endgroup$ – user155234 Nov 26 '14 at 22:47
  • $\begingroup$ See Theorem 4.18 of the book of Stewart-Tall "Algebraic Number Theory and Fermat's Last Theorem". $\endgroup$ – Crostul Nov 26 '14 at 23:16
  • 1
    $\begingroup$ math.stackexchange.com/questions/23844/… $\endgroup$ – cactus314 Dec 4 '14 at 15:30

I think it is important to remember that Euclid's GCD algorithm is what motivates the definition of a Euclidean domain. For example, in $\mathbb{Z}$, if I ask you to compute $\gcd(7, 30)$, your mind automatically comes up with the answer, but if you have any doubt you can always use Euclid's GCD algorithm to assure yourself the answer is correct. Along the way you might think about how $30 = 4 \times 7 + 2$. But you probably won't think about how $30 = 10 \times 7 - 40$, which is true, but irrelevant to the task at hand because $N(-40) > N(7)$ (here I'm using $N(n) = \sqrt{n^2}$, where $\sqrt{n}$ gives the principal square root, just in case you're curious).

Before we tackle $\mathcal{O}_{\mathbb{Q}(\sqrt{-19})}$, let's look at a UFD that is a Euclidean domain, $\mathbb{Z}[\sqrt{-2}]$. What is $\gcd(\sqrt{-2}, 2 + 2\sqrt{-2})$? My gut feeling is that the answer is $\sqrt{-2}$. But I'm not sure this is correct, so I use Euclid's algorithm: $2 + 2\sqrt{-2} = (2 - \sqrt{-2}) \times \sqrt{-2} + 0$. Clearly $N(0) < N(\sqrt{-2})$ (now I'm using $N(a + b\sqrt{-2}) = a^2 + 2b^2$). This confirms my hunch that $\gcd(\sqrt{-2}, 2 + 2\sqrt{-2}) = \sqrt{-2}$. Of course this is insufficient to prove that $\mathbb{Z}[\sqrt{-2}]$ is norm-Euclidean, but that was not my purpose here.

But it does suggest that to find an example where "Euclideanness" fails, we need to choose numbers in $\mathcal{O}_{\mathbb{Q}(\sqrt{-19})}$ such that one number is not a divisor of the other, because in that case we can just do $r = 0$ and determine $q$ accordingly. Our norm function is now $N\left(\frac{a}{2} + \frac{b\sqrt{-19}}{2}\right) = \frac{a^2}{4} + \frac{19b^2}{4}$. Let's try $\gcd\left(\frac{3}{2} + \frac{\sqrt{-19}}{2}, 10\right)$. How about $\left(\frac{3}{2} - \frac{\sqrt{-19}}{2}\right) \times \left(\frac{3}{2} + \frac{\sqrt{-19}}{2}\right) + 3$? But $N(3) > N\left(\frac{3}{2} + \frac{\sqrt{-19}}{2}\right)$. And if we try $2\left(\frac{3}{2} - \frac{\sqrt{-19}}{2}\right) \times \left(\frac{3}{2} + \frac{\sqrt{-19}}{2}\right) - 4$ we run into a similar problem: $N(-4) > N\left(\frac{3}{2} + \frac{\sqrt{-19}}{2}\right)$. Hmm, let's see about $\left(\frac{1}{2} - \frac{\sqrt{-19}}{2}\right) \times \left(\frac{3}{2} + \frac{\sqrt{-19}}{2}\right) + \left(\frac{9}{2} + \frac{\sqrt{-19}}{2}\right)$. This is much worse, for now we have $25 > 7$ rather than just $9 > 7$.

I'm going to try one more thing: $\left(\frac{5}{2} - \frac{\sqrt{-19}}{2}\right) \times \left(\frac{3}{2} + \frac{\sqrt{-19}}{2}\right) + \left(\frac{3}{2} - \frac{\sqrt{-19}}{2}\right)$. This is the worst attempt so far, because $7 = 7$ exclamation mark! If we were working in $\mathbb{Z}$, running into b == r would probably prompt us to q++ (by which I mean q := q + 1) and r := 0. Suffice it to say that trying this here would lead us to $r = \sqrt{-19}$ and clearly $19 > 7$.

It's up to you if you want to continue the wild goose chase or read R. A. Wilson's 2011 proof that $\mathcal{O}_{\mathbb{Q}(\sqrt{-19})}$ is a principal ideal domain but not Euclidean. I will close by remarking that Euclid's GCD algorithm is not the only one for finding the GCD. If you can factorize into primes, you can figure out the GCD that way.

  • 1
    $\begingroup$ Very good answer. One detail, though, I think that instead of "because otherwise we can just do $r = 0$" you should have written "because if one number is a divisor of the other we can just do $r = 0$". $\endgroup$ – user153918 Dec 1 '14 at 15:11
  • $\begingroup$ But can't you just do this? $$0 \times 10 + \left(\frac{3}{2} + \frac{\sqrt{-19}}{2}\right)$$ Then $10$ has a norm of $100$ and $\left(\frac{3}{2} + \frac{\sqrt{-19}}{2}\right)$ has a norm of $7$. $\endgroup$ – Bill Thomas Dec 4 '14 at 23:26
  • $\begingroup$ That's true, but $q = 0$ does nothing to advance the algorithm. $\endgroup$ – Robert Soupe Dec 5 '14 at 3:42
  • 1
    $\begingroup$ I agree. You can always do $q = 0$ and it gives you nothing. Also, in a Euclidean domain, you can choose the "wrong" modulus in Euclids' algorithm and still get the right answer. I'm looking at Giblin's Pascal program for GCD in $\mathbb{Z}$: it doesn't check that $a > b$, but if you give it an input like that it "naturally" switches them and then proceeds. So @BillThomas, how do we proceed from $0 \times 10 + (\frac{3}{2} + \frac{\sqrt{-19}}{2})$? Giblin's program suggests we then look for $\gcd(10, (\frac{3}{2} + \frac{\sqrt{-19}}{2}))$. Its put us right back where we started! $\endgroup$ – user155234 Dec 5 '14 at 22:37

Your Answer

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