$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 8.3: Euclidean Domains

• • Tom Denton
$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

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])