This page covers section 3.7 (“Euclidean Rings”). Throughout, is a ring.
Topics covered: 3.7
Definition: The integral domain is a Euclidean ring if there exists such that
For , there exist with and either or .
Here, is the set of non-negative integers. This generalizes the Euclidean algorithm of the integers.
Theorem 3.7.1: If is an ideal of the Euclidean ring , then there exists such that . In other words, must be principal.
Definition: A principal ideal domain (PID) is a ring all of whose ideals are principal. By Theorem 3.7.1, a Euclidean ring is always a PID.
Corollary: A Euclidean ring is unital.
Definition: Let be commutative and let with . divides , or , if there exists with .
Definition: Let be commutative and let with . is a greatest common divisor of and if and and, if and , then .
Lemma 3.7.1: Let be Euclidean and let be non-zero. There exists a greatest common divisor of and , and there exist such that .
Definition: Let be commutative and unital. Element is a unit if there exists with .
Lemma 3.7.2: Let be an integral domain and let be such that and . Then for some unit .
Definition: Let be commutative and unital and let . If there exists a unit such that , then and are associates.
Lemma 3.7.3: Let be Euclidean and let . If is not a unit, then .
Definition: Let be Euclidean. A non-unit is prime if, with , implies that one of or is a unit.
Lemma 3.7.4: Let be Euclidean. Every element in is either a unit or expressible as a finite product of prime elements in .
Definition: Let be Euclidean and let . and are relatively prime if their greatest common divisor is a unit in .
Lemma 3.7.5: Let be Euclidean and let be such that but . Then .
Lemma 3.7.6: Let be Euclidean and let with prime. If then divides or or both.
Theorem 3.7.2 (unique factorization): Let be Euclidean and let be non-zero. It is possible to factorize as a product of primes, and that factorization is unique up to multiplication by units. In particular, the number of primes in the product is the same for any such factorization.
Lemma 3.7.7: An ideal of Euclidean ring is maximal if and only if is prime.
The problems below are paraphrased from/inspired by those given in Topics in Algebra by Herstein. The solutions are my own unless otherwise noted. I will generally try, in my solutions, to stick to the development in the text. This means that problems will not be solved using ideas and theorems presented further on in the book.
Herstein 3.7.1: Let be commutative and unital. Show that the relation if is an associate of is an equivalence relation.
is reflexive: so that .
is symmetric: If , then suppose is the unit such that . There exists with , and multiplying by this gives and therefore .
is transitive: If and , then there are units with and . Of course, and, because is a unit, . is a unit because there exists with , and .
Herstein 3.7.2: Let be Euclidean. Prove that any two greatest two common divisors of are associates.
Let and be two greatest common divisors of and . If divides both and , then it must also divide a greatest common divisor. In particular, must, as a divisor of and , divide . Then for some . By the same token, there exists such that . Then , or . We have so that and are units, and therefore and are associates.
Alternately, we can appeal to Lemma 3.7.2.
Herstein 3.7.3: Let be Euclidean. Prove that is a unit if and only if .
If is a unit, then there exists with . We have that . This looks promising, but what precludes from being something big, and fitting comfortably beneath it? Well, we also have , and so we conclude that .
On the other hand, if , then we would like to show that is a unit. By the Euclidean algorithm, there exists such that and either or . It is, however, impossible for to be smaller than . To see this, consider that while by assumption! Therefore we have and so that is a unit.
Herstein 3.7.4: Let be Euclidean and let . Prove that their greatest common divisor may be found by
Clearly, by the Euclidean algorithm, each step in the procedure is acceptable in its own right. We also see that it will terminate in the form for some , because the norms of the remainders constitute a monotonically decreasing sequence in the positive integers (as defined by Herstein, the remainder can either be zero or smaller in norm than the divisor, because the norm of the zero element is not defined). The non-trivial statement here is that this terminating divisor, , is in fact
Stepping up the chain, we have that
so that . Iterating this easily shows that for all . Then also
Thus we have proven, or at least sketched a proof, that divides both and .
If we can additionally prove that for some , then we will be done. Why? If is another divisor of both and , then and so that . But this is actually easy to see. If we re-arrange each step of the algorithm, we find that and , and so forth. Proceeding in this way, we can express every remainder as a linear combination of and . Finally, we arrive at
which is at last rearranged into the form .
Notice that we are implicitly working in the ideal . Theorem 3.7.1 showed that any ideal of a Euclidean ring is actually principal, that is, generated by a single element. Lemma 3.7.1 showed further that this ideal is generated by a greatest common divisor of and . Of course, there may be lesser common divisors, for instance while and . The lesser common divisors, however, do not gain entrance to our ideal! Put another way, they may not be expressed as a linear combination of and . Out of all simultaneous divisors, only a greatest common divisor admits a representation as a linear combination of and .
Herstein 3.7.5: Let be commutative and unital. Prove that if an ideal of contains a unit, then .
Suppose there is a unit so there exists such that . Let be arbitrary. We have so that and therefore .
Herstein 3.7.6: Let be commutative and unital. Prove that the units of form an abelian group.
Let be the set of units of . We will let inherit the associative, commutative ring multiplication. Of course, so that . Letting , we have such that . This also means that and hence contains inverses. Finally, we note that if , then is also a unit. There exist such that and . Then so that and the set is closed under multiplication.
Herstein 3.7.7: Let be Euclidean and let . A least common multiple of and is a number such that (1) and , and (2) if is such that and , then . Prove that and have a least common multiple in .
The existence of a greatest common divisor was shown in Lemma 3.7.1, where the ideal was employed. We seek another natural ideal to consider. Clearly we want to look at elements of which are multiples of both and . The multiples of are the ideal while the multiples of are the ideal . The intersection of those ideals,
is again an ideal and its elements are exactly those which are divisible by both and . By Theorem 3.7.1, is generated by some element and we claim that is a least common multiple of and . As , we have that and . If is such that and , then and so . Therefore we have exhibited a least common multiple of and .
Herstein 3.7.8: Let be Euclidean and let . Denoting least common multiple by and greatest common divisor by , show that .
By Theorem 3.7.2, we can express
with the and prime elements of . We can construct a greatest common divisor of and by iterating through the list and picking out those primes which also appear in the list of (up to associates). Taking this subset of the and computing its product gives a ring element , which will be a greatest common divisor. It is clear, because it is a product of primes which divide both and , that and . Furthermore, any other with and must have : suppose it were otherwise, then there would be a prime with , so therefore and , but . This contradicts the construction of . Therefore is a greatest common divisor of and .
Now that the list of has been pared down somewhat, we can take a product over the remaining and over all of the , and call this product . Because nothing has been removed from , we see that both and : still contains all of the primes that were common to and , and retains whatever was left over from after the culling. If is another multiple of and , so and , then we must have : suppose it were otherwise, then there would be a prime with but not . Of course, every prime dividing must divide one or both of and , so this would show that could not be a common multiple. Therefore we must have and hence is a least common multiple of and .
Finally, we have that
which is the desired result.