abstract-algebraeuclidean-algorithm
This picture is an example in Dummit and Foote's Abstract Algebra. It shows that $\mathbb{Z}[\sqrt{-5}]$ is not a Euclidean domain by showing that the field norm $N(a+b\sqrt{-5})=a^2+5b^2$ doesn't allow the euclidean algorithm.
But why only showing the field norm not okay is enough?
Alright, this is from the viewpoint of what is called "covering radius" for positive quadratic forms. You have a quadratic form $f(x,y) = x^2 - 6 y^2.$ Now, with any real point $(a,b)$ in the plane, you want to find an integer point $(m,n)$ such that $$|f(a-m, b-n)| < 1. $$
Now, what is the set, centered around $(0,0)$ with $| x^2 - 6 y^2| < 1?$ It is a strange starfish shape with four arms, all along lines of slope $\pm \frac{1}{\sqrt 6}.$ The starfish "centered at" some integer point $(m,n)$ is $$ |(x -m)^2 - 6 (y - n)^2 | < 1. $$
All that is needed to show your inequality is that a finite set of such starfish covers the ordinary unit square with corners at $(0,0),(1,0),(1,1),(0,1).$
Well, the square $0 \leq x \leq 1, \; \; 0 \leq y \leq 1 $ is covered by eight starfish centered at $$ (0,0),(0,1), (1,0),(1,1), (-1,0),(-1,1),(2,0),(2,1). $$ The four starfish centered at the corners of the square itself cover all except a funny curvy diamond shape around $(\frac{1}{2}, \frac{1}{2} ),$ the vertices of the diamond being $$ \left(\frac{1}{2}, \frac{1}{2} \sqrt{\frac{5}{6}} \right), \; \left(\frac{1}{2}, 1 - \frac{1}{2} \sqrt{\frac{5}{6}} \right), \; \left(\frac{1}{\sqrt2}, \frac{1}{2} \right), \; \left( 1 -\frac{1}{\sqrt2}, \frac{1}{2} \right). $$ Next, out of the four remaining squares, the (open) starfish centered at $(-1,0)$ covers the entire closed rectangle $$ \frac{1}{5} \leq x \leq \frac{1}{2}, \; \; \frac{1}{2} \leq y \leq \frac{3}{5}, $$ so you can see that the four final starfish cover the closed rectangle $$ \frac{1}{5} \leq x \leq \frac{4}{5}, \; \; \frac{2}{5} \leq y \leq \frac{3}{5}, $$ thus entirely covering the missing diamond shape.
Earlier I had a solution with $20$ points, this is easier. Still, I suggest you have a computer draw the intersections of these sets with the square I indicate. I did this with a calculator and some graph paper, but I have special eyes.
September 2016: by computer, a bit much. Maybe if I show just the first four starfish, the central diamond that is not yet covered should be more clear
Note that the four boundary curves of the starfish centered at the integer point $(m,n)$ can be parametrized by a variable $t$ as $$ \left( m + \cosh t, \; n + \frac{ \;\sinh t \;}{\sqrt 6} \right), $$ $$ \left( m - \cosh t, \; n + \frac{ \;\sinh t \;}{\sqrt 6} \right), $$ $$ \left( m + \sinh t, \; n + \frac{ \;\cosh t \;}{\sqrt 6} \right), $$ $$ \left( m + \sinh t, \; n - \frac{ \;\cosh t \;}{\sqrt 6} \right). $$
EDITTT: this was first proved by Perron in 1932, with a better method by Oppenheim in 1934. See page 11 in survey.pdf at LEMMERMEYER
What I'm about to say is based on two results I have not verified for myself. First, I take it on faith that $\mathbb{Z}[\sqrt{23}]$ is a principal ideal domain and therefore a unique factorization domain. Second, that if a ring is Euclidean it has a universal side divisor, and that an element of minimum norm among non-units in an Euclidean ring is a universal side divisor.
Since $N(5 + \sqrt{23}) = 2$ and we're dealing with a unique factorization domain, it follows that any number in this domain with even norm is divisible by $5 + \sqrt{23}$. If a number in this domain has odd norm, then it suffices to add or subtract $1$ to it to make it a number of even norm.
Then for $\gcd(a, b)$ where $a \neq 0$ and $b = 5 + \sqrt{23}$, we can always find a suitable $q \neq 0$ such that $a = qb \pm 1$; obviously $|N(a)| \geq 1$. Therefore $5 + \sqrt{23}$ is a universal side divisor and therefore also $\mathbb{Z}[\sqrt{23}]$ is an Euclidean domain.
I take your word for it that you can prove that this domain is not norm-Euclidean. I'm guessing the minimal example of norm-Euclidean failure is $\gcd(4 + \sqrt{23}, 5)$, you'll let me know if that's wright or wrong. I have no idea what the Euclidean function could be.
Best Answer
Read the proof more carefully. They actually show that $I$ is not principal (using methods related to the field norm) and then use the fact that any euclidean domain is a principal ideal domain.