<s>[INST] 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.
 [/INST] 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$.
</s>