# Proof that $\mathbb Z[\sqrt{3}]$ is a Euclidean Domain

Let $R_d$ be the ring defined as $R_d=\left \{ x+y\omega : x,y\in \mathbb{Z} \right\}$, where $$\omega = \begin{cases} \sqrt{d}, & \text{if } \quad d \not \equiv 1\mod 4 \\ \frac{1+\sqrt{d}}{2}, & \text{if } \quad d\equiv 1\mod 4. \end{cases}$$

It has been proven that $R_d$ is Euclidean for several positive values of $d$.

Does anyone know where I can find a proof that $R_d$ is Euclidean for $d=3$?

Thank you.

Define the norm on $$\mathbb Z[\sqrt 3]$$ to be $$N(a + b \sqrt 3) = \vert a^2 - 3 b^2 \vert$$.

Let $$\alpha, \beta \in \mathbb Z[\sqrt 3]$$ with $$\beta \neq 0$$.

Say $$\alpha = a + b \sqrt 3$$ and $$\beta = c + d \sqrt 3$$.

Notice that \begin{align*} \frac\alpha\beta &= \frac{a + b \sqrt 3}{c + d \sqrt 3} \cdot \frac{c - d \sqrt 3}{c - d \sqrt 3} \\ &= \frac{ac - 3bd}{c^2 - 3d^2} + \frac{-ad + bc}{c^2 - 3d^2} \sqrt 3 \\ &= r + s\sqrt 3 \end{align*}

where $$r = \displaystyle \frac{ac - 3bd}{c^2 - 3d^2}$$ and $$s = \displaystyle \frac{-ad + bc}{c^2 - 3d^2}$$.

Let $$p$$ be the closest integer to $$r$$ and let $$q$$ be the closest integer to $$s$$. Notice that $$\vert r - p \vert \leq 1/2$$ and $$\vert s - q \vert \leq 1/2$$.

We want to show that $$\alpha = (p + q\sqrt 3) \beta + \gamma$$ for some $$\gamma \in \mathbb Z[\sqrt 3]$$ such that either $$\gamma = 0$$ or $$N(\gamma) < N(\beta)$$. (We'll show the latter holds always.)

Define $$\theta := (r - p) + (s - q)\sqrt 3$$ and define $$\gamma = \beta \cdot \theta \in \mathbb Z[\sqrt 3]$$ and observe that \begin{align*} \gamma &= \beta \cdot \theta\\ &= \beta ( (r - p) + (s - q)\sqrt 3)\\ &= \beta (r + s\sqrt 3) - \beta(p + q\sqrt 3) \\ &= \beta \cdot\frac\alpha\beta - \beta (p + q\sqrt 3) \\ &= \alpha - \beta (p + q\sqrt 3) \end{align*}

Hence we have $$\alpha = \beta(p + q\sqrt 3) + \gamma$$.

Finally notice that \begin{align*} N(\gamma) &= N(\beta \cdot \theta) \\ &= N(\beta) \cdot N(\theta) \\ &= N(\beta) \cdot \vert (r - p)^2 - 3 (s - q)^2 \vert \\ &\leq N(\beta) \cdot \max\{ (r - p)^2, 3(s - q)^2\} \\ & \leq\frac34 N(\beta)\\ &< N(\beta) \end{align*}

The key here was that $$\vert (r - p)^2 - 3 (s - q)^2 \vert \leq \max\{ (r - p)^2, 3(s - q)^2\}$$ since $$(r - p)^2, 3(s - q)^2 \geq 0$$ and then we use that $$(r - p)^2 \leq 1/4$$ and $$3(s - q)^2 \leq 3/4$$.

• When you're proving that $N(\gamma) < N(\beta)$, you say that $N(\theta) = |(p-r)^2 - 3(q-s)^2|$. However, $N$ was only defined for elements in $\Bbb{Z}[\sqrt{3}]$. You showed that $(\beta)(\theta) \in \Bbb{Z}[\sqrt{3}]$. But how does this imply that $\theta \in \Bbb{Z}[\sqrt{3}]$? – Artus Mar 12 '15 at 14:05
• That's a very good question! We can just think of the norm $N$ on $\mathbb Z[\sqrt 3]$ as being the norm on $\mathbb Q[\sqrt 3]$, restricted to $\mathbb Z[\sqrt 3]$. – Robert Cardona Mar 12 '15 at 15:13
• why is |p - r |< 1/2 and |q- s| < 1/2 – user10024395 Apr 23 '15 at 9:33
• @user136266, because we define $p, q$ to be the closest integers to $r, s$, respectively. Say $p = \frac14$, the closest integer is $0$ and the difference is less than $\frac12$, if $p = \frac34$, then the closest integer is $1$. If $p = \frac12$, then pick either $0$ or $1$ and the claim holds (less than or equal to). – Robert Cardona Apr 23 '15 at 14:21
• @RobertCardona how is 1/4 and 1/2 integers? these are not integers. i think you meant r but even so why must r be only these 3 possibilities?If i have a, c = 1 and b,d = 0. Then r = 0 and so u can't find an integer p such that p-r < 1/2. – user10024395 Apr 24 '15 at 1:45