What is a concrete example to demonstrate that $\mathcal{O}_{\mathbb{Q}(\sqrt{-19})}$ is NOT a norm-Euclidean domain? I'm talking about the ring of algebraic integers of the form $\frac{a}{2} + \frac{b \sqrt{-19}}{2}$, where $a, b \in \mathbb{Z}$.
This ring is said to be a principal ideal domain but not a Euclidean domain to any suitable function.
Since its not norm-Euclidean, it should be possible to find specific numbers $n, b, q, r \in \mathcal{O}_{\mathbb{Q}(\sqrt{-19})}$ such that $n = qb + r$ yet $N(r) > N(b)$. Or would the failure of Euclideanness manifest itself in some other way?
I've looked at a few different books and papers, and alot of them give a concrete example (usually $6$) for $\mathbb{Z}[\sqrt{-5}]$ not being UFD, but no example to show $\mathcal{O}_{\mathbb{Q}(\sqrt{-19})}$ is PID but not Euclidean with respect to some function.
 A: I think it is important to remember that Euclid's GCD algorithm is what motivates the definition of a Euclidean domain. For example, in $\mathbb{Z}$, if I ask you to compute $\gcd(7, 30)$, your mind automatically comes up with the answer, but if you have any doubt you can always use Euclid's GCD algorithm to assure yourself the answer is correct. Along the way you might think about how $30 = 4 \times 7 + 2$. But you probably won't think about how $30 = 10 \times 7 - 40$, which is true, but irrelevant to the task at hand because $N(-40) > N(7)$ (here I'm using $N(n) = \sqrt{n^2}$, where $\sqrt{n}$ gives the principal square root, just in case you're curious).
Before we tackle $\mathcal{O}_{\mathbb{Q}(\sqrt{-19})}$, let's look at a UFD that is a Euclidean domain, $\mathbb{Z}[\sqrt{-2}]$. What is $\gcd(\sqrt{-2}, 2 + 2\sqrt{-2})$? My gut feeling is that the answer is $\sqrt{-2}$. But I'm not sure this is correct, so I use Euclid's algorithm: $2 + 2\sqrt{-2} = (2 - \sqrt{-2}) \times \sqrt{-2} + 0$. Clearly $N(0) < N(\sqrt{-2})$ (now I'm using $N(a + b\sqrt{-2}) = a^2 + 2b^2$). This confirms my hunch that $\gcd(\sqrt{-2}, 2 + 2\sqrt{-2}) = \sqrt{-2}$. Of course this is insufficient to prove that $\mathbb{Z}[\sqrt{-2}]$ is norm-Euclidean, but that was not my purpose here.
But it does suggest that to find an example where "Euclideanness" fails, we need to choose numbers in $\mathcal{O}_{\mathbb{Q}(\sqrt{-19})}$ such that one number is not a divisor of the other, because in that case we can just do $r = 0$ and determine $q$ accordingly. Our norm function is now $N\left(\frac{a}{2} + \frac{b\sqrt{-19}}{2}\right) = \frac{a^2}{4} + \frac{19b^2}{4}$. Let's try $\gcd\left(\frac{3}{2} + \frac{\sqrt{-19}}{2}, 10\right)$. How about $\left(\frac{3}{2} - \frac{\sqrt{-19}}{2}\right) \times \left(\frac{3}{2} + \frac{\sqrt{-19}}{2}\right) + 3$? But $N(3) > N\left(\frac{3}{2} + \frac{\sqrt{-19}}{2}\right)$. And if we try $2\left(\frac{3}{2} - \frac{\sqrt{-19}}{2}\right) \times \left(\frac{3}{2} + \frac{\sqrt{-19}}{2}\right) - 4$ we run into a similar problem: $N(-4) >  N\left(\frac{3}{2} + \frac{\sqrt{-19}}{2}\right)$. Hmm, let's see about $\left(\frac{1}{2} - \frac{\sqrt{-19}}{2}\right) \times \left(\frac{3}{2} + \frac{\sqrt{-19}}{2}\right) + \left(\frac{9}{2} + \frac{\sqrt{-19}}{2}\right)$. This is much worse, for now we have $25 > 7$ rather than just $9 > 7$.
I'm going to try one more thing: $\left(\frac{5}{2} - \frac{\sqrt{-19}}{2}\right) \times \left(\frac{3}{2} + \frac{\sqrt{-19}}{2}\right) + \left(\frac{3}{2} - \frac{\sqrt{-19}}{2}\right)$. This is the worst attempt so far, because $7 = 7$ exclamation mark! If we were working in $\mathbb{Z}$, running into b == r would probably prompt us to q++ (by which I mean q := q + 1) and r := 0. Suffice it to say that trying this here would lead us to $r = \sqrt{-19}$ and clearly $19 > 7$.
It's up to you if you want to continue the wild goose chase or read R. A. Wilson's 2011 proof that $\mathcal{O}_{\mathbb{Q}(\sqrt{-19})}$ is a principal ideal domain but not Euclidean. I will close by remarking that Euclid's GCD algorithm is not the only one for finding the GCD. If you can factorize into primes, you can figure out the GCD that way.
