# Visualizing Euclidean Algorithm in $\mathbb{Q}(\sqrt{-7})$ and $\mathbb{Q}(\sqrt{-11})$ with Convex Geometry

In an attempt to answer one of the bounty questions, I have started picturing Euclidean division in quadratic fields. In theory we would like the equation:

$$a = b\,q + r \hspace{0.25in}\text{with}\hspace{0.25in} N(r) < \tfrac{1}{2}N(b)$$

The ring of integers of $\mathbb{Q}(i)$ is $\mathbb{Z}[i]$ and the norm is $||a + bi|| = \sqrt{a^2 + b^2}$, so it seems like it should be enough to show the sumset ( or Minkowski sum)

$$\mathbb{Z}[i] + \left\{ x^2 + y^2 < \tfrac{1}{2} \right\} = \mathbb{C}$$

and the picture confirms that Euclidean division should neatly hold in $\mathbb{Z}[i]$ with room to spare.

For $\mathbb{Q}(i \sqrt{3})$ we can find the ring $\mathbb{Z}\left[\frac{1+i\sqrt{3}}{2}\right]$ with norm $||a + \omega b|| = \sqrt{ a^2 + ab + b^2 }$. Euclidean geometry is helping is out so far.

The corresponding result for $\mathbb{Q}(i \sqrt{7})$ almost looks right but I see tiny patches missing and by $\mathbb{Q}(i \sqrt{11})$ forget it. Wikipedia says there the norm-Euclidean quadratic fields are $d = -1,-3,-7,-11$ and no more.

Why is my picture of the Euclidean algorithm inaccurate? And how to we get the missing points?

• i think you want $N(r) < N(b)$ instead of $N(r) < N(b)/2$ Commented May 21, 2015 at 16:53
• @mercio over $\mathbb{Z}$ we say $a = bq + r$ with $0 < r < b$. The interval $[0,b]$ is the "circle" with diameter $b$. We could just as easily say $|r| < \tfrac{1}{2}b$ and get a slightly different Euclidean algorithm. Commented May 21, 2015 at 16:57
• yes but we can also choose a remainder $r$ with $-b < r < b$ (a circle with radius $b$), and by induction the algorithm will still terminate. Commented May 21, 2015 at 18:01
• Convex geometry or convex analysis? Commented Apr 25, 2022 at 18:08