Let be a squarefree integer. Let be the quadratic field with associated quadratic integer ring and field norm given by if and if , where if and if . (Recall that .)

- Prove that if then is a Euclidean domain with respect to the norm .
- Prove that if then is not a Euclidean domain with respect to any norm.

[With help from Planet Math.]

Let be a squarefree integer, and let if and if .

First we prove that is a Euclidean domain for . That is, for all with , there exist such that and .

To that end, let and . In , we have , where and . Let be an integer closest to and an integer closest to . Then and . Now let ; certainly . Now let , and let . In , we have , so that . Then , and moreover . It remains to be shown that . To that end, note that . For , this yields , as desired.

Now we show that is a Euclidean domain for . But first, a lemma.

Lemma: If is a squarefree integer such that and , then . Proof: If , then evidently , where certainly 2 divides . Consider , with . Evidently, , which is in .

Now to the desired result: Let and . Suppose such that . Then there exist such that and , where .

To see this, let and . Note that, in , we have , where and . Choose to be an integer closest to . Then we have , and thus . Next, choose to be an integer closest to . Let ; then we have . Let . Certainly is divisible by 2, so that . Next, let , and let . Note that , so that is in . Moreover we have . It remains to be shown that ; to that end, note that . For , we have , as desired.

Note that our proof is constructive, so that we can easily compute the division algorithm explicitly in these rings or (even better) write a program to do it. Moreover, we can get a bound on how quickly the Euclidean algorithm terminates; for , at each step we have , for instance.

Finally, we show that is not a Euclidean domain for . To achieve this, we will show that contains no universal side divisors. Recall that if is an integral domain, then an element is called a universal side divisor if for every , there exist elements and such that . It is a fact that every Euclidean domain contains universal side divisors; thus if a domain does not contain universal side divisors it cannot be Euclidean with respect to any norm. We begin with some lemmas.

Lemma: Let be an integral domain with . If is a universal side divisor, then and are universal side divisors. Proof: Since is a universal side divisor, for all there exist and such that . Thus is a universal side divisor, and since is commutative, so is .

Let be a squarefree integer such that , , and , let , and suppose that is a universal side divisor. Note that by the lemma, we may assume that ; otherwise, we can write where has this property. Now we know that the units in are 1 and -1 (for any ). Thus here . Let ; then it must be the case that divides one of , , or . By definition cannot be a unit, so that cannot divide 1. Thus divides either 2 or 3.

Suppose divides 2, and we have . Taking the norm of both sides, we have . In particular, since is not a unit, we have . More generally, . Note that , so that by the hypothesis, . We can see by checking all the cases (there are 4 of them) that this equation has only one solution in , namely the zero solution, with . But this contradicts our assumption that and are relatively prime. Thus cannot divide 2.

Suppose instead that divides 3, with . Then as above, we have , and . Again by our hypothesis, this yields . Note that the squares mod 3 are 0 and 1. Checking all four possibilities for and , we see that this equation has only the solution , again contradicting the relative primeness of and . Thus cannot divide 3.

Thus we have shown that contains no universal side divisors, and thus cannot be a Euclidean domain. (We have proved this in fact for a much larger class of quadratic integer rings than was requested here.)