# How do I prove whether something is a Euclidean domain?

Is there a "special formula" one can follow to prove whether something is a Euclidean domain or not? I've been looking around, but I haven't seemed to be able to find one, so I was wondering whether I was blind, or there just isn't one.

I have $\mathbb Z[\sqrt-3]=\{x+y\sqrt-3|x,y\in\mathbb Z\}$. I think I can remember having read somewhere that it's a Euclidean domain, but I'm not sure. I also don't know how to prove it. Any hints?

-
It's not actually. In fact, for every $n\geq 3$ square-free, $\mathbb{Z}[\sqrt{-3}]$ is not even a UFD. The idea is to show that $2$ is irreducible but not prime (show that 2 divides a certain product without dividing one of the factors). On the other hand, $\mathbb{Z}[i]$ and $\mathbb{Z}[\sqrt{-2}]$ are both Euclidean. –  JessicaB Nov 27 '12 at 23:37
In comparison, see en.wikipedia.org/wiki/Eisenstein_integers –  Will Jagy Nov 27 '12 at 23:41
On the other hand, the integers of ${\mathbb{Q}}[\sqrt{-3}]$ are Euclidean, and this is probably what OP had in mind. –  Lubin Nov 27 '12 at 23:49
@Lubin: I don't think so, given the OP's definition of $\Bbb Z[\sqrt{-3}]$. –  Cameron Buie Nov 27 '12 at 23:56
I think I must have confused $\mathbb Q [\sqrt-3]$ with $\mathbb Z [\sqrt-3]$. Thank you for clearing that up! It's a lot easier to prove something when you actually know what it is you're supposed to prove. –  Cathrine Nov 28 '12 at 0:06

Hint: $$4=(2)(2)=(1-\sqrt{-3})(1+\sqrt{-3}).$$

-

To prove something is or is not a Euclidean domain, it seems useful to use the following chart:

Fields $\subset$ Euclidean Domain $\subset$ Principal Ideal Domain $\subset$ Unique Factorization Domain $\subset$ Domain

In particular, to prove something is a Euclidean domain, you may prove either it is a field (only if it actually is a field), or you may prove it is a Euclidean domain directly (See below for details).

To prove something is not a euclidean domain, you may prove that it is not one of the latter ones: i.e., prove there exists an ideal that is not principal, a factorization that is not unique, or zero divisors.

To prove something is a euclidean domain, by and large you must prove the existence of a division algorithm using the standard definition that $\forall x,y \in D \exists q,r$ satisfying $$x = qy + r$$ and $\mathcal{N}(r) < \mathcal{N}(y)$, where $\mathcal{N}$ is a norm on your domain $D$.

-

To my knowledge, given an arbitrary integral domain, there is no "general" method to figure out whether it is a Euclidean domain.

To expand a bit on JessicaB's comment, though, we can completely determine which of the rings of the form $$\Bbb Z[\sqrt{-n}]:=\{a+b\sqrt{-n}:a,b\in\Bbb Z\}$$ are Euclidean domains (where $n$ is some positive integer). Let me outline how one might do it.

Given a positive integer $n$, we define $\rho_n$ from $\Bbb Z[\sqrt{-n}]$ to the nonnegative integers by $$\rho_n(a+b\sqrt{-n}):=a^2+b^2n.$$ This function will tell us important things about the ring. Some useful facts to prove are:

(A) $\rho_n$ is a multiplicative function--that is, $\rho_n(x\cdot y)=\rho_n(x)\cdot\rho_n(y)$.

(B) $x\in\Bbb Z[\sqrt{-n}]$ is a unit of $\Bbb Z[\sqrt{-n}]$ if and only if $\rho_n(x)=1$, and $x=0$ if and only if $\rho_n(x)=0$.

(C) If $x,y\in\Bbb Z[\sqrt{-n}]$ are associates (that is, differ by multiplication by a unit), then $\rho_n(x)=\rho_n(y)$. (The converse doesn't hold, though. Consider $1\pm2\sqrt{-n}$.)

(D) If $x\in\Bbb Z[\sqrt{-n}]$ is nonzero and not a unit, then $x=x_1\cdots x_k$, where each $x_j$ is irreducible in $\Bbb Z[\sqrt{-n}]$. (That is, we have existence, though not necessarily uniqueness, of irreducible factorizations.)

(E) If $n\geq 2$, then $\sqrt{-n}$ is irreducible in $\Bbb Z[\sqrt{-n}]$.

(F) If $n\geq 3$, then $2$ is irreducible in $\Bbb Z[\sqrt{-n}]$.

Having these handy facts in our arsenal, it isn't too difficult to prove the following two results:

($1$) If $n=1$ or $n=2$, then $\Bbb Z[\sqrt{-n}]$ is a Euclidean domain, with Euclidean function $\rho_n$.

($2$) If $n\geq 3$ (whether $n$ is square-free or not), then $\Bbb Z[\sqrt{-n}]$ is not a UFD, so not a Euclidean domain. [As JessicaB pointed out, you need only show that $2$ is not prime in $\Bbb Z[\sqrt{-n}]$. You may want to do two cases, for $n$ odd and $n$ even.]

-
Is $\Bbb Z [x]$ a ED? I Think its not because we can show that Ideal $I=(2,x)$ in $\Bbb Z[x]$ is not principal. that implies $\Bbb Z[x]$ is not PID. Therefore its not ED. –  Sara Tancredi Nov 20 '13 at 2:22
You are correct. It is not a PID, so not a ED. –  Cameron Buie Nov 20 '13 at 2:31
No, complex numbers $\Bbb C$ is an ED trivially, as it is a field, Now $Q[\sqrt{-5}]$ is a subring of $\Bbb C$ but not a ED. does this counter example work? –  Sara Tancredi Nov 20 '13 at 2:47
It does, indeed! Well done. In fact, $\Bbb Z[\sqrt{-n}]$ is not even a UFD for integers $n\ge 3,$ as I mention in my answer, so even a subring of a field need not be a UFD! The best we can say for a subring of a ED is that it is an integral domain. –  Cameron Buie Nov 20 '13 at 2:56
I'm afraid that's outside my experience. That would probably be a good question to ask in an official capacity, though. I'm sure someone on the site will know! –  Cameron Buie Nov 20 '13 at 3:07