# 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.

-
Also, I have looked at the "integer lattice" technique described here mathreference.com/num,gi.html#gcd... I'm not sure if I'm allowed to use that since we haven't encountered in it class. – Ziggy Oct 26 '12 at 17:58
In general, there is no "division algorithm" in $\mathbb Z[\sqrt n]$ for arbitrary $n$. When there is a division algorithm which is suitable for computing $\gcd$, all ideals are principal, and then $\mathbb Z[\sqrt n]$ has unique factorization into primes. – Thomas Andrews Oct 26 '12 at 18:02
The "quick" way to divide is by dividing $(a+b\sqrt{n})(c-d\sqrt{n})$ by $(c+d\sqrt n)(c-d\sqrt n)=c^2-nd^2$. But that doesn't generally give you a "remainder" that is "smaller" in the useful sense that you can do the Euclidean algorithm with it. – Thomas Andrews Oct 26 '12 at 18:08

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)

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 one can find examples of such results in the papers below. If memory serves correct the first paper sparked a letter to the editor that some of the 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.

-
I'd upvote this for showing your work, if it wasn't for that your answer is obviously far too technical to be helpful to the OP... – tomasz Oct 26 '12 at 19:41
@tomasz Most of the answer can be comprehended by anyone who has mastered a first course in algebra. And, of course, one is welcome to ask for elaboration. – Bill Dubuque Oct 26 '12 at 19:57
@Gone that was amazing! Correct me if I'm wrong but I think the answer to my question is then that UFD's have the right kind of division, but that finding the Euclidean algorithm is difficult? – Ziggy Jan 4 '13 at 17:56

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

-
It is one if... n is square-free? Or something? – Ziggy Oct 26 '12 at 18:23
@Ziggy, only some square free n are. – sperners lemma Oct 26 '12 at 19:18