11
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ i think you want $N(r) < N(b)$ instead of $N(r) < N(b)/2$ $\endgroup$
    – mercio
    Commented May 21, 2015 at 16:53
  • $\begingroup$ @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. $\endgroup$
    – cactus314
    Commented May 21, 2015 at 16:57
  • 1
    $\begingroup$ 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. $\endgroup$
    – mercio
    Commented May 21, 2015 at 18:01
  • $\begingroup$ Convex geometry or convex analysis? $\endgroup$
    – Rodrigo de Azevedo
    Commented Apr 25, 2022 at 18:08

1 Answer 1

Reset to default
3
$\begingroup$

Following Mercio's comment, it's still the Euclidean algorithm if we make the ovals 2× as big.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .