8.3: Euclidean Domains

Creating a field of fractions is one way to definitively solve the problems of division in an integral domain: Make up fractions to have an inverse for every non-zero element. But there's (sometimes) another way to define division without resorting to introducing new elements to the field, familiar from the integers: define division using a 'quotient' and a 'remainder.'

For example, among the integers we can write \(25 = 8\cdot 3+1\); then \(25/\mathord 3\) has a quotient \(8\) and remainder \(1\). Generally, to find \(n/\mathord m\), we write \(n= qm+r\), where \(0<r<|m|\). Then \(q\) is the quotient and \(r\) is the remainder.

We can do something similar with polynomials: Given two polynomials \(f\) and \(g\), we can divide \(f\) by \(g\) and uniquely write \(f=Qg+R\), where \(Q\) is a polynomial and \(R\) is a polynomial of lower degree than \(g\).

For example, take \(f=2x^5+3x^2+x+3\) and \(g=x^2+1\), we can apply the polynomial long division algorithm and get \(f= (2x^3-2x+3)g -x\). Here \(2x^3-2x+3\) is the whole part and \(-x\) is the remainder.

In both the integer division and the polynomial division, the key ingredient is a way of ordering the elements of the ring: in the integers, we order by the usual ordering of the integers, and with polynomials we order by the degree of the polynomial.

Definition 8.2.0: Norm on a Ring

A norm on a ring \(R\) is a function \(n: R\rightarrow \mathbb{Z}_{\geq 0}\) with \(n(0)=0\). A positive norm has \(n(r)>0\) for all \(r\neq 0\).

Any given ring can have many different norms. The norm on the integers is simply the absolute value of the integer; it is a positive norm. The norm on polynomials is the degree of the polynomial.

Definition 8.2.1: Euclidean Domain

A Euclidean domain is an integral domain \(R\) with a norm \(n\) such that for any \(a, b\in R\), there exist \(q,r\) such that \(a=q\cdot b + r\) with \(n(r)<n(b)\). The element \(q\) is called the quotient and \(r\) is the remainder.

A Euclidean domain then has the same kind of partial solution to the question of division as we have in the integers.

In fact, Euclidean domains further have a Euclidean algorithm for finding a common divisor of two elements. The Euclidean algorithm is performed by starting with two elements \(f\) and \(g\) for which we wish to find a common divisor. Dividing \(f\) by \(g\) gives a quotient \(q_0\) and a remainder \(r_0\). We then divide \(g\) by \(r_0\) and obtain a new quotinet \(q_1\) and a new remainder, \(r_1\). We then repeat this process to get quotients \(q_2, q_3, \ldots q_k\) and remainders \(r_2, r_3, \ldots r_k\). Each remainder has smaller norm than the previous, so this process must eventually terminate with some \(r_k=0\).

The final quotient, \(q_k\) divides both \(g\) and \(f\): You can see this by writing \(f=q_0g+r_0\), and then expanding \(r_0\): \(f=q_0(q_1r_0 + r_1)+r_0\). If we imagine the process ending at this point, so that \(r_1=0\), we then have \(r_0\) divides both \(f\) and \(g\). On the other hand, if the process doesn't terminate, we can expand \(r_0=q_2r_1+r_2\). Then \(f=q_0(q_1(q_2r_1+r_2) + r_1)+q_2r_1+r_2\). If the process terminates, then \(r_2=0\), and \(r_1\) divides every term, and thus divides \(f\) and \(g\). If the process doesn't terminate, we repeat the same basic argument.

(TODO: Examples in Z and Z[x])

Contributors and Attributions

• Tom Denton (Fields Institute/York University in Toronto)