Can we do long division in $\mathbb Z[\sqrt n]$, where $n$ is square free?

Question

Can we do long division of elements $a + b\sqrt n$ and $c + d\sqrt n$ in $\mathbb Z[\sqrt n]$? I gave it a shot, but wasn't sure how to proceed... I'd like to use the gcd algorithm to show that two ideals <a,b> and <c> in that set are equal.

Also, the norms of those elements can tell us things about the elements. Like, if the norms are prime then the elements are irreducible? So could finding the gcd of norms shed light on the equality of these ideals? My text book gives one example in Z of using gcd(a,b) = c to conclude that <a,b> = <c>, but doesn't give any examples of this failing, or of its application in complex extensions.

Thanks,

a.

Answer 1

Any integral domain that enjoys division with "smaller" remainder, i.e. any Euclidean domain, is necessarily a UFD (unique factorization domain), by essentially the same proof as for $\Bbb Z$. Thus any ring of quadratic integers which is not a UFD will have no such division algorithm. However, there is a (nonconstructive) converse: Weinberger proved in 1973, assuming GRH, that a UFD number ring R with infinitely many units is Euclidean. Thus, for example, real quadratic number rings are Euclidean $\iff$ UFD. However, constructing this Euclidean algorithm can be a very difficult task, e.g. this was proved only in the last decade for $\rm\,\Bbb Z[\sqrt{14}]\,$ (Harper). For a deeper understanding of Euclidean number fields see the excellent surveys by Hendrik Lenstra in Mathematical Intelligencer 1979/1980 (Euclidean Number Fields 1,2,3) and Franz Lemmermeyer's authoritative survey The Euclidean algorithm in algebraic number fields.

However, there is a sort of generalization of the division algorithm that serves to characterize PIDs (number rings, having dimension $1$ are UFD $\iff$ PID). Namely the so-called Dedekind-Hasse criterion states that a domain is a PID iff given any two nonzero elts $\rm\:a, b \in D,\:$ either $\rm\:a\:|\:b\:$ or some D-linear combination $\rm\:a\,d+b\,c\:$ is "smaller" than $\rm\,a.\,$ It is clear that such a domain must be PID (since then the "smallest" element in an ideal must divide all others). Conversely, since a PID is UFD, an adequate metric is the number of prime factors (if $\rm\,a\nmid b\:$ then their gcd $\rm\,c\,$ must have fewer prime factors; for if $\rm\:(a,b) = (c)\:$ then $\rm\,c\:|\:a\:$ properly, else $\rm\,a\:|\:c\:|\:b\:$ contra hypothesis). Clearly the Euclidean descent via the Division Algorithm is just a special case, so Euclidean $\Rightarrow$ PID ($\Rightarrow$ {UFD,Bezout} $\Rightarrow$ GCD domain)

In fact it is not-so-well-known folklore that one can generalize such results to ideals and this lends even further insight, e.g. see the the following two papers of Clifford Queen for some such results

Queen, C. Euclidean-like characterizations of Dedekind, Krull, and factorial domains.
J. Number Theory 47 (1994), no. 3, 359--370.

Queen, C. Factorial domains
Proc. Amer. Math. Soc. 124 (1996), no. 1, 11--16.

Answer 2

In general, $\mathbb Z[\sqrt n]$ need not be an euclidean ring.