Associated Topics || Dr. Math Home || Search Dr. Math

### D is Not Euclidean

```Date: 02/20/2003 at 07:34:41
Subject: Euclidean domain

Let a be a negative integer. Show that Z[a^0.5] is a Euclidean
domain if and only if a = -1 or a = -2.
```

```
Date: 02/22/2003 at 09:36:24
From: Doctor Jacques
Subject: Re: Euclidean domain

Let D = Z[sqrt(d)] be the domain under consideration.

For convenience, we will write w = sqrt(d); as we are interested in
d < 0, w is a purely imaginary complex number.  We will write a|b to
mean that a divides b.

D consists of the complex numbers x + yw, for all integer x, y.

Remember that an integral domain A is Euclidean if there exists a
function f : A - {0} -> N, such that, for any non-zero a, b in A:

(1) if a | b, then f(a) <= f(b)
(2) there exists q and r in A such that a = bq + r and either r = 0 or
f(r) < f(b).

We will first prove that D is a Euclidean domain for d = -1 or -2,
when we take as function f the norm:

f(x + yw) = N(x + yw) = x^2 - dy^2.

This function is defined for any complex number; in fact:

f(x + iy) = x^2 + y^2.

It is rather obvious that f(z) is an integer >= 1 for all non-zero z
in D.

Note also that f(z) = |z|^2, where |z| is the complex modulus
(absolute value) of z.  This implies the multiplicative property:

f(z_1*z_2) = f(z_1)*f(z_2)

This should allow you to prove property (1) easily (this is true for
all negative integers d).

To prove property (2), we rewrite the equation as:

r/b = (a/b) - q

Because of the particular choice of the function f, f(r) < f(b) is
equivalent to:

f(r/b) < 1

or

f((a/b) - q) < 1

The ratio a/b can be written as s + tw, where s and t are rational
numbers (you can check this by rationalizing the denominator).

If s and t are integers, a/b belongs to D, and we set q = a/b and
r = 0.  In this case, property (2) is satisfied.

Assume now that this is not the case.

We must find an element q of D, q = x + yw, such that:

f((r + sw) - (x + yw)) < 1

which means:

(r - x)^2 - d*(s - y)^2 < 1

We take x and y as the integers closest to r and s, respectively.
This implies:

|r - x| <= 1/2
|s - y| <= 1/2

This gives

(r - x)^2 - d*(s - y)^2 <= 1/4 - d/4 <= 3/4 < 1

because -d <= 2, by hypothesis.

There is a geometric interpretation of this.  D can be represented as
a 2-dimensional lattice in the complex plane, where a fundamental
region is the rectangle (0, 1, w, 1 + w).

The relation

f((a/b) - q) < 1

is equivalent to

|(a/b) - q| < 1

and property (2) will always be satisfied if every element a/b is
within distance less than 1 of a lattice point, or, equivalently, if
we can cover the complex plane with open discs of radius 1 centered
at the lattice points.

If is easy to see that this will be the case if the half-diagonal of
the fundamental rectangle is < 1, and this corresponds to |d| < 3.

This also proves that, if d <= -3, we cannot use the function f above
as a Euclidean function.  However, it could still be the case that D
would be a Euclidean domain, but with a different Euclidean function.

We will now prove that this is not the case.  This is a little more
complicated, and I'm not sure you are really required to prove it.

We will first assume that d < -3; the case d = -3 will be handled
separately.

Assume, by contradiction, that d < -3 and there is a Euclidean
function g (we do NOT assume that g is the norm we used above). We
keep the notation N(z) to mean |z|^2 :

N(x + yw) = x^2 - dy^2.

Let us select an element a from D such that N(a) > 1, and g(a) is
minimal subject to that condition.  We can find such an element
because g takes only positive integer values.

Consider any element b of D. We have:

b = aq + r

with r = 0 or g(r) < g(a).

Because of the choice of a, this implies that r = 0 or N(r) = 1.

It is easy to see that the only elements of D with norm 1 are +1 and
-1.  We can therefore conclude that r = 0, 1, or -1.

This means that there are at most three equivalence classes modulo a,
or that the index in D of the ideal <a> is at most 3.

The ideal <a> (the set of multiples of a) is a sub-lattice generated
by the vectors a and aw.  The index of that ideal is the ratio of the
areas of the fundamental regions.

Let a = r + sw.  The basis vectors for <a> are r + sw and rw + sw^2 =
rw + ds.

If we let v = |w| = sqrt(-d), these vectors can be written as:

r + isv
ds + irv

where i is the imaginary unit, and everything else is real.

The area of the fundamental region of <a> is given, by the absolute
value of the determinant:

|r  sv| = v(r^2 - ds^2)
|ds rv|

The area of the fundamental region of D is given by:

|1  0| = v
|0  v|

and the index of <a> is therefore (r^2 - ds^2).

Another way to see this is to notice that, if we multiply every
element of D by a (as complex numbers), the area of the fundamental
region is multiplied by |a|^2.

Our condition becomes:

(r^2 - ds^2) <= 3

As d <= -4, it is easily seen that the only solutions are s = 0,
r = (+/-)1, which means that a = +1 or -1, and N(a) = 1.  But this
contradicts the choice of a, and shows therefore that D is not
Euclidean.

So far, we have shown:

* D is a Euclidean domain, with the norm as Euclidean function, for
d = -1 or -2

* These are the only negative d for which D is a Euclidean domain
with the norm as Euclidean function.

* If d <= -4, D is not Euclidean.

We still have to settle the case D = -3, with a Euclidean function
other than the norm.

Assume d = -3.

If D is Euclidean, it admits unique factorization.  However, we have
the two factorizations:

4 = 2*2 = (1 + w)(1 - w)

These factorizations are irreconcilable, because:

* the factors are not associate: (1+w)/2 and (1-w)/2 do not belong
to D.

* the factors are irreducible.  As N(2) = 4, any proper factor q of 2
would have N(q) = 2, and it is easy to see that the equation
x^2 + 3y^2 = 2
has no integer solution.

This shows that D does not admit unique factorization, and is
therefore not Euclidean.

some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 02/24/2003 at 04:51:14
Subject: Thank you (Euclidean domain)

Thank you very very much.

```

```
Date: 12/20/2004 at 04:26:22
From: Ahcool
Subject: Re: Quadratic Fields and the Division Algorithm

The reply says that one needs to prove the division algorithm does
not exist for the norm map. However this is not sufficient since we
need to prove that such algorithm does not exist for ANY "degree"
map.

So my question is whether there is any quick way of showing that,
something like Z [(1+sqrt(-19))/2] is NOT a Euclidean domain?

This is a typical hard question since this ring is known to be a
principle ideal domain and hence a unique factorization domain BUT
NOT a Euclidean domain.

It is relatively easy to show that such a division algorithm does not
exist for the norm map. But it's hard to prove, however, for ANY map.
```

```
Date: 12/20/2004 at 07:33:37
From: Doctor Jacques
Subject: Re: Quadratic Fields and the Division Algorithm

Hi Ahcool,

http://mathforum.org/library/drmath/view/62284.html

which is referred to in the article you mention. The proof starts at
the paragraph:

-----
Assume, by contradiction, that d < -3 and there is a Euclidean
function g (we do NOT assume that g is the norm we used above)....
-----

As explained in that article, we assume that there is a Euclidean
function g (what you call a "degree" map), but we *do not* assume
that g is the usual norm. We keep the notation N(x) for the usual
norm.

The idea of the proof is to pick a non-zero element a such that a is
not a unit and for which g(a) is minimal (as g takes only positive
integer values, as any Euclidean function, such an element exists).

We then proceed to show that any element of D is congruent to -1, 0,
or 1 (mod ) - this is explained in the article. This means that
there are at most three congruence classes modulo , and therefore
the index of the ideal  in D is at most 3.

The index of the ideal  is N(a) - the usual norm (NOT g(a)). This
means that, if a = r + s*sqrt(d), we have:

N(a) = r^2 - d*b^2 <= 3

As d <= -4, or, equivalently, (-d) >= 4 this implies:

r^2 + 4*b^2 = 3

and the only integer solution is a = (+/-) 1, which means that a is a
unit, and this contradicts our choice of a.

The above proof only applies to rings of the form Z(sqrt(d)). If
d = 1 (mod 4) the ring D of integers of Q(sqrt(d)) also contains
other elements; the general element of D is of the form:

R/2 + (S/2)*sqrt(d)

where R and S are integers, both odd or both even. In that case, the
discriminant of D is -d (instead of -4d), and the proof must be
modified. The condition in this case is d < -11 (for d >= -11, the
usual norm can be used as a Euclidean function).

Assume now that d < -11, and d = -1 (mod 4). Note that this implies
d <= -15. We have:

N(a) = (R^2)/4 -d*(S^2)/4 <= 3

As -d >= 15, this gives:

(R^2)/4 + 15*(S^2)/4 <= 3

As 15/4 > 3, we must have S = 0, and R must be even. We have
R^2 <= 12, and therefore R = 2 or -2, and a = 1 or -1. Once again,
this contradicts the fact that a is not a unit.

some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 09/13/2004 at 18:48:36
From: Vanyo
Subject: is Z[w], w = (1+sqrt(-7)) / 2 a Euclidean domain

I am trying to prove that Z[w], w = (1+sqrt(-7)) / 2, is a Euclidean
domain.  I get to the point where I want to have that
|| beta/alpha - q || must be < 1.  But I find that it could also be 1.
Am I wrong or is it just that Z[w] is not Euclidean?
```

```
Date: 09/14/2004 at 03:38:44
From: Doctor Jacques
Subject: Re: is Z[w], w = (1+sqrt(-7)) / 2 a Euclidean domain

Hi Vanyo,

The article above refers to the case where w = sqrt(d), for d
a negative integer.  In this case, we have w = (1+sqrt(-7))/2,
and the argument must be slightly modified.

It is still true that we must check that every complex number is
within distance 1 of a lattice point; however, in this case, the
fundamental domain is a parallelogram, not a rectangle.  This means
that we must select the lattice point with more care.

We pick an arbitrary complex number x + iy, and we must find a
suitable lattice point:

z = r + sw = (r+s/2) + i(s*sqrt(7))/2

It is natural to try to have the real and imaginary parts of
(x + yi - z) as small as possible.

Let us start with the imaginary part, y - s*sqrt(7)/2.  We take s as
the integer closest to 2y/sqrt(7).  This will give us:

| 2y/sqrt(7) - s | <= 1/2
| y - s*sqrt(7)/2 | <= sqrt(7)/4

Now, we turn to the real part, x - r - s/2.  If we select r as the
integer closest to (x - s/2), we will have:

| x - r - s/2 | <= 1/2

Putting both relations together, we get:

N(x + yi - z) = (x - r - s/2)^2 + (y - s*sqrt(7)/2)^2
<= 1/4 + 7/16
< 1

as desired.

some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Modern Algebra

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search