Can we do long division in $\mathbb Z[\sqrt n]$, where $n$ is square free? 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.
 A: 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+bc\:$ 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, which yields
$$\text{ Euclidean $\Rightarrow$ PID ($\Rightarrow$ \{UFD, Bezout\} $\Rightarrow$ GCD domain})\qquad$$
It is not-so-well-known folklore that these and related results can be
generalized to ideals, e.g. as I mentioned on Ask an Algebraist 2008/12/5 there are examples of such results in the papers below. If memory serves correct the first paper sparked a letter to the editor that various results are very old.
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.

As for how well the divisibility theory of the ambient ring of integers is (faithfully) reflected in the divisibility of its norms, see  this answer.
A: In general, $\mathbb Z[\sqrt n]$ need not be an euclidean ring.
