3.4 Principal Ideal Domains and Euclidean Domains

Back

Let R be an integral domain, and let d : R − {0} ! N [ {0} be a function

satisfying the so-called division algorithm

Given a, b 2 R, a 6= 0, there exist q, r 2 R such that b = qa + r and either

r = 0 or d(r) < d(a).

If the above holds we say that R (or more precisely the pair (R, d)) is a

Euclidean domain. The function d is often called an algorithm . It is possible

for a Euclidean domain to have more than one algorithm; see Exercises 7,

9. Furthermore, we have not insisted that the elements q (quotient) and

r (remainder) are unique. However, this is the case in the following two

prototypical examples below:

(i) R = Z, d(n) = |n|.

(ii) R = F[x], where F is a field, and d(f(x)) = deg f(x).

There are others; see Exercises 1, 4.

In most textbook treatments of Euclidean domains, one requires the

algorithm d to satisfy a submultiplicativity condition:

d(a) _ d(ab) for all a, b 2 R − {0}.

Such an algorithm is called a submultiplicative algorithm; this assumption is

unnecessary; see Exercise 6, below.

As I remarked in Section 3.3, these domains are p.i.d.’s:

Theorem 3.4.1 If R is a Euclidean domain, then R is a principal ideal

domain.

From Theorem 3.3.4, Section 3.3, we conclude the following.

Theorem 3.4.2 (Fundamental Theorem of Arithmetic) Z is a u.f.d.

Finding principal ideal domains which are not Euclidean domains is

tricky. Here’s an example. (For details, see Larry Grove, Algebra, Academic

Press, New York, 1983, pages 63, 66.) Let

R = {(a + b

p

−19)/2| a, b 2 Z, a _ b(mod 2)}.

3.4. PRINCIPAL IDEAL DOMAINS AND EUCLIDEAN DOMAINS 85

Then R is a p.i.d. but is not Euclidean. (If you are wondering about the

“2” in the denominators of elements of R, good! In the next chapter we’ll

see that nature forces this on us.)

Exercises

1. The ring of Gaussian integers is defined by setting R = {a + bi| a, b 2

Z}. If we set d(a + bi) = a2 + b2, show that d gives R the structure

of a Euclidean domain. (Hint: Let a, b 2 R, a 6= 0. Do the division in

the field Q[i]; say

b

a

= h + ki, h, k 2 Q.

Now choose integers x, y such that |x − h|, |y − k| _ 1

2 , and set q =

x+yi, r = b−qa. Show that d(r) _ 1

2d(a).) Note that relative to the

algorithm d, quotient and remainder need not be unique.

2. The above method can actually be used to prove that the domain

R = {a + b

p

n| a, b 2 Z}, n = −2,−1, 2, 3 is a Euclidean domain.

Prove this.

3. Express the following ideal as principal ideals:

(a) (3 + i) + (7 + i) _ Z[i].

(b) {4a + 2b

p

2| a, b 2 Z} _ Z[

p

2].

4. Let _ = e2_i/3. Show that the domain R = {a + b_| a, b 2 Z} is

Euclidean.

5. Prove that Z[i] _= Z[x]/(x2 + 1).

6. Let (R, d) be a Euclidean domain. Define a new function d0 : R−{0} !

N [ {0} by setting

d0(r) = min

s2Rr−{0}

d(s), r 2 R.

Prove that d0 is a submultiplicative algorithm.

7. Consider the following function on the ring Z of integers.

d(n) =

_

|n| if n 6= 1

2 if n = 1

Prove that d is a non-submultiplicative algorithm on Z.

86 CHAPTER 3. ELEMENTARY FACTORIZATION THEORY

8. Let R be an integral domain, and define subsets Ri, i = 0, 1, . . . inductively,

as follows:

(i) R0 = {0}.

(ii) If i > 0 set R0

i = [j<iRj . Define

Ri = {0} [ {r 2 R| R0

i ! R/(r) is surjective}.

Prove that R is Euclidean if and only if R = [i_0Ri, in which case we

can take d(r) = i if and only if r 2 Ri − R0

i . (For a detailed discussion

of the above result, see P. Samuel, About Euclidean rings, J. Algebra,

19, 282-301 (1971).)

9. Let R = Z, the ring of integers. Show that the map d, constructed as

in Exercise 8 above is given by

d(n) = number of binary digits of |n|.

10. This exercise contains an algorithm similar to that of Exercise 8 (for

details, see T. Motzkin, The Euclidean algorithm, Bull. Amer. Math.

Soc. 55, 1142-1146 (1949)). Define subsets Ri, i = 0, 1, . . . inductively,

as follows:

(i) R0 = R − {0}.

(ii) If i > 0 set

Ri+1 = {r 2 Ri| there exists a 2 R with a + Rr _ Ri}.

Prove that R is Euclidean if and only if \i_0Ri = ;, in which case we

can take d(r) = i if and only if r 2 Ri − Ri+1.

11. Let R = Z, the ring of integers. Show that the map d, constructed as

in Exercise 8 above is given by

d(n) = number of binary digits of |n|.

Chapter 4 Dedekind Domains

Навигация