# 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. Commented Oct 26, 2012 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. Commented Oct 26, 2012 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. Commented Oct 26, 2012 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 (recall number rings, having dimension $$\,1\,$$ are  UFD $$\!\iff\!$$ PID). The Dedekind-Hasse criterion states that a domain is a PID iff given any two nonzero elts $$\rm\:a, b \in D,\:$$ if $$\rm\:a\nmid b\:$$ then 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 "smaller" measure 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 little-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 some results are 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.

• 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... Commented Oct 26, 2012 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. Commented Oct 26, 2012 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? Commented Jan 4, 2013 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? Commented Oct 26, 2012 at 18:23
• @Ziggy, only some square free n are. Commented Oct 26, 2012 at 19:18