Euclidean domains

Theorem: Polynomial division

Let be a commutative ring and such that the leading coefficient is a unit in . Then, for every there are unique such that where .

Proof:

Claim

for every .
Proof:
Clear if . Otherwise, so .

We now first prove existence. Let and . We induct on . If , then meaning we can pick . Now assume . If then we can choose and and we are done. Now assume . Then, consider which cancels out the highest degree term, meaning , so by induction can be divided with remainder, and plugging everything in we are done.

We now prove uniqueness. Let such that and where . We then get and we have but also , meaning , so .

Definition: Euclidean domain

A Euclidean domain is an integral domain together with a map that satisfies that for every and there are such that where or . is called the Euclidean function or degree function.

In summary, we need some notion of the remainder of division being "smaller" than the divisor. In the context of integers, it is just being smaller in an absolute sense, but for polynomials it's the degrees being smaller. Also, any field is a Euclidean domain with any function since division is always defined in with zero rest.

Theorem

Every Euclidean domain is a PID.

Proof:
Let be the Euclidean delta function on , and let . Then, if it is principal so we are done. Now assume , and choose an such that is minimal. Let . Then for some where or . But we have so we can't have , meaning so , meaning .

Not every PID is a Euclidean domain though. A horrific example is which is a non-Euclidean PID.

Also, from this theorem we immediately know that is a PID.

Euclidean algorithm

Let be a Euclidean domain. The Euclidean algorithm takes and outputs a of and .

First, let and .
Then, for if then , and if then compute and such that and or .
Return such that and .

Proof:
For , the sequence of is strictly decreasing (as long as ) meaning it must at some point hit . Furthermore, for and we have and if and only if and , meaning any of and is also a of and . Hence , which is a of and , is a of and .

Corollary: Extended Euclidean algorithm

Let be a Euclidean domain and . Then the Eucliden algorithm yields such that the returned is .

Proof:
From the Euclidean algorithm we will have , , and so on until we have . By isolating the remainders, we see that in the end, is a sum of multiples of and multiples of .

Corollary:

The extended Euclidean algorithm can be used to compute a , , of many elements , and to find such that .

Proof:
Exercise, but show that .

Theorem

Let be an integral domain and . Then, if , then is a of . In particular, in PID's, 's always exist.

Proof:
Since every , we know , so is a common divisor. Also, since we have , so is a .

Corollary

In PID's, the implication in Theorem Theorem is an equivalence.

Proof:
Since is a PID, for some . Then is a . In integral domains 's are unique up to units, so for any we have , in particular, .