# 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
• 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. – MBrown Nov 28 '12 at 0:06
• There is no special formula. You can prove some examples by similar methods (I am thinking of ${\mathbf Z}[i]$, ${\mathbf Z}[\sqrt{2}]$, and ${\mathbf Z}[\sqrt{-2}]$). But for other Euclidean domains you need a new "trick". If you learn algebraic number theory then you will see that there is a unifying viewpoint for showing certain rings of numbers (like ${\mathbf Z}[\sqrt{-3}]$, but not that exactly) are PIDs, but even if they are Euclidean the method for showing they are PIDs bypasses the Euclidean issue entirely. – KCd Nov 28 '12 at 0:52

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

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

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