Polynomials and fields · Definition

Euclidean domain

modern algebrarings

Before you start you need to know

It is the most general setting in which the Euclidean algorithm works, and the first class of domains that guarantees a factorization into irreducibles as orderly as that of the integers.

Definition

An integral domain \(D\) with a norm \(N\) (a function from \(D\setminus\{0\}\) to the nonnegative integers) allowing division of \(a\) by \(b\neq0\) with quotient \(q\) and remainder \(r\) zero or of smaller norm than \(b\).

\[a=bq+r,\qquad r=0\ \text{ or }\ N(r)

The basic examples are \(\mathbb{Z}\) with \(N(n)=|n|\), the ring \(F[x]\) over a field with \(N(f)=\deg f\), and the Gaussian integers \(\mathbb{Z}[i]\) with \(N(a+bi)=a^2+b^2\). In all three, dividing means finding a "smaller" remainder than the divisor. The quotient and remainder need not be unique: in \(\mathbb{Z}[i]\), \(7+3i\) can be divided by \(2\) in more than one way, and it is enough that one exists.

Repeated division is the Euclidean algorithm: \(a=bq_1+r_1\), \(b=r_1q_2+r_2\), and so on. Since the norms \(N(r_1)>N(r_2)>\cdots\) are nonnegative integers, the process stops, and the last nonzero remainder is a greatest common divisor of \(a\) and \(b\). Working the steps backwards gives \(\gcd(a,b)=ax+by\), the Bézout identity.

The central structural consequence is that every Euclidean domain is a principal ideal domain: a nonzero ideal is generated by any of its elements of minimal norm. The converse is false; there are principal ideal domains that admit no Euclidean norm. And \(\mathbb{Z}[x]\), with its non-principal ideal \((2,x)\), is left out. Later we will see that every principal ideal domain is a unique factorization domain.

Think about it

Why does the Euclidean algorithm stop in a Euclidean domain?

Because the norms of the successive remainders form a strictly decreasing sequence of nonnegative integers, which cannot be infinite.

Is \(\mathbb{Z}\) also a Euclidean domain with the norm \(N(n)=n^2\)?

Yes: \(n^2<m^2\) is equivalent to \(|n|<|m|\), so the same division works. The norm of a Euclidean domain is not unique.

Exercises 10

  1. In \(\mathbb{Z}\) with \(N(n)=|n|\), which quotient \(q\) and remainder \(r\) satisfy \(17=5q+r\) with \(0\le r<5\)?
  2. Which function works as a Euclidean norm on \(F[x]\), with \(F\) a field?
  3. In the Gaussian integers \(\mathbb{Z}[i]\) the norm \(N(a+bi)=a^2+b^2\) is used. What is \(N(3+4i)\)?
  4. In \(\mathbb{Z}\), use the Euclidean algorithm to compute \(\gcd(252,198)\).
  5. In \(\mathbb{Q}[x]\), what is the greatest common divisor of \(x^3-1\) and \(x^2-1\)?
  6. In \(\mathbb{Z}[i]\) with \(N(a+bi)=a^2+b^2\), which is a valid division of \(7+3i\) by \(2\) (that is, \(7+3i=2q+r\) with \(r=0\) or \(N(r)<N(2)\))?
  7. In \(\mathbb{Q}[x]\), compute the monic greatest common divisor of \(x^{3} - x^{2} + x - 1\) and \(x^{3} + x^{2} + x + 1\).
  8. If \(D\) is a Euclidean domain, what can be said about its ideals?
  9. To prove that an ideal \(I\neq0\) of a Euclidean domain is principal, which element is taken as generator?
  10. Which of these domains is not Euclidean?

References

  • David S. Dummit, Richard M. Foote, Abstract Algebra, 3rd edition, Wiley, 2004. §8.1
  • Joseph A. Gallian, Contemporary Abstract Algebra, 9th edition, Cengage, 2017. cap. 18
  • I. N. Herstein, Abstract Algebra, 3rd edition, Wiley, 1996. §3.7
  • John B. Fraleigh, A First Course in Abstract Algebra, 7th edition, Pearson, 2002. §46
  • Serge Lang, Algebra, Revised 3rd edition, Springer, 2002. cap. II §5