Topics in Algebra, Chapter 3.7

2013-01-13 math algebra topics-in-algebra

This page covers section 3.7 (“Euclidean Rings”). Throughout, R is a ring.

Topics covered: 3.7

  • Definition: The integral domain R is a Euclidean ring if there exists d:R0Z such that

    1. d(a)d(ab) for a,bR0.

    2. For a,bR0, there exist r,sR with a=sb+r and either r=0 or d(r)<d(b).

    Here, Z is the set of non-negative integers. This generalizes the Euclidean algorithm of the integers.

  • Theorem 3.7.1: If I is an ideal of the Euclidean ring R, then there exists aR such that I=(a)={axxR}. In other words, I 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 R be commutative and let a,bR with a0. a divides b, or ab, if there exists cR with b=ac.

  • Definition: Let R be commutative and let a,b,dR with a,b0. d is a greatest common divisor of a and b if da and db and, if ca and cb, then cd.

  • Lemma 3.7.1: Let R be Euclidean and let a,bR be non-zero. There exists a greatest common divisor dR of a and b, and there exist r,sR such that d=ra+sb.

  • Definition: Let R be commutative and unital. Element aR is a unit if there exists bR with ab=1.

  • Lemma 3.7.2: Let R be an integral domain and let a,bR be such that ab and ba. Then a=ub for some unit uR.

  • Definition: Let R be commutative and unital and let a,bR. If there exists a unit uR such that a=ub, then a and b are associates.

  • Lemma 3.7.3: Let R be Euclidean and let a,bR. If b0 is not a unit, then d(a)<d(ab).

  • Definition: Let R be Euclidean. A non-unit πR is prime if, with a,bR, π=ab implies that one of a or b is a unit.

  • Lemma 3.7.4: Let R be Euclidean. Every element in R is either a unit or expressible as a finite product of prime elements in R.

  • Definition: Let R be Euclidean and let a,bR. a and b are relatively prime if their greatest common divisor is a unit in R.

  • Lemma 3.7.5: Let R be Euclidean and let a,b,cR be such that abc but (a,b)=1. Then ac.

  • Lemma 3.7.6: Let R be Euclidean and let a,b,πR with π prime. If πab then π divides a or b or both.

  • Theorem 3.7.2 (unique factorization): Let R be Euclidean and let aR be non-zero. It is possible to factorize a 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 I=(a) of Euclidean ring R is maximal if and only if a 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 R be commutative and unital. Show that the relation ab if a is an associate of b is an equivalence relation.

Let r,s,tR.

  1. is reflexive: r=r1 so that rr.

  2. is symmetric: If rs, then suppose uR is the unit such that r=su. There exists uR with uu=1, and multiplying by this u gives s=ru and therefore sr.

  3. is transitive: If rs and st, then there are units u,vR with r=su and s=tv. Of course, r=t(uv) and, because uv is a unit, rt. uv is a unit because there exists u,vR with uu=vv=1, and (uv)(uv)=1.

Herstein 3.7.2: Let R be Euclidean. Prove that any two greatest two common divisors of a,bR are associates.

Let d1 and d2 be two greatest common divisors of a and b. If c divides both a and b, then it must also divide a greatest common divisor. In particular, d2 must, as a divisor of a and b, divide d1. Then d1=d2r for some rR. By the same token, there exists sR such that d2=d1s. Then d1=d1rs, or d1(1rs)=0. We have rs=1 so that r and s are units, and therefore d1 and d2 are associates.

Alternately, we can appeal to Lemma 3.7.2.

Herstein 3.7.3: Let R be Euclidean. Prove that aR is a unit if and only if d(a)=d(1).

If a is a unit, then there exists bR with ab=1. We have that d(a)d(ab)=d(1). This looks promising, but what precludes d(1) from being something big, and d(a) fitting comfortably beneath it? Well, we also have d(1)d(a1)=d(a), and so we conclude that d(a)=d(1).

On the other hand, if d(a)=d(1), then we would like to show that a is a unit. By the Euclidean algorithm, there exists t,rR such that 1=ta+r and either r=0 or d(r)<d(a). It is, however, impossible for d(r) to be smaller than d(a). To see this, consider that d(1)d(r1)=d(r) while d(a)=d(1) by assumption! Therefore we have r=0 and at=1 so that a is a unit.

Herstein 3.7.4: Let R be Euclidean and let a,bR. Prove that their greatest common divisor (a,b) may be found by

b=q0a+r1whered(r1)<d(a)a=q1r1+r2whered(r2)<d(r1)r1=q2r2+r3whered(r3)<d(r2)rn1=qnrnandrn=(a,b).\begin{aligned} b=q_0 a+r_1\qquad & {\rm where}\qquad d(r_1)<d(a)\ a=q_1 r_1+r_2\qquad & {\rm where}\qquad d(r_2)<d(r_1)\ r_1=q_2 r_2+r_3\qquad & {\rm where}\qquad d(r_3)<d(r_2)\ \cdots & \ r_{n-1}=q_n r_n\qquad & {\rm and}\qquad r_n=(a,b). \end{aligned}

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 rn1=qnrn for some n, 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, rn, is in fact (a,b).

Stepping up the chain, we have that rn2=qn1rn1+rn=(qn1qn+1)rn

so that rnrn2. Iterating this easily shows that rnri for all 0<i<n. Then also rn(q1r1+r2)=a

and rn(q0a+r1)=b.

Thus we have proven, or at least sketched a proof, that rn divides both a and b.

If we can additionally prove that rn=λa+μb for some λ,μR, then we will be done. Why? If cR is another divisor of both a and b, then cλa and cμb so that crn. But this is actually easy to see. If we re-arrange each step of the algorithm, we find that r1=1bq0a and r2=aq1r1=(1+q0q1)aq1b, and so forth. Proceeding in this way, we can express every remainder as a linear combination of a and b. Finally, we arrive at rn2=qn1rn1+rn

which is at last rearranged into the form rn=λa+μb.

Notice that we are implicitly working in the ideal I(a,b)={ra+sbr,sR}. 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 I(a,b) is generated by a greatest common divisor of a and b. Of course, there may be lesser common divisors, for instance (4,8)=4 while 24 and 28. 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 a and b. Out of all simultaneous divisors, only a greatest common divisor admits a representation as a linear combination of a and b.

Herstein 3.7.5: Let R be commutative and unital. Prove that if an ideal I of R contains a unit, then I=R.

Suppose there is a unit uI so there exists vR such that uv=1. Let rR be arbitrary. We have u(vr)=(uv)r=rI so that RI and therefore I=R.

Herstein 3.7.6: Let R be commutative and unital. Prove that the units of R form an abelian group.

Let U(R) be the set of units of R. We will let U(R) inherit the associative, commutative ring multiplication. Of course, 11=1 so that 1U(R). Letting uU(R), we have vR such that uv=1. This also means that vU(R) and hence U(R) contains inverses. Finally, we note that if u1,u2U(R), then u1u2 is also a unit. There exist v1,v2R such that u1v1=1 and u2v2=1. Then u1u2v1v2=1 so that u1u2U(R) and the set is closed under multiplication.

Herstein 3.7.7: Let R be Euclidean and let a,bR. A least common multiple of a and b is a number cR such that (1) ac and bc, and (2) if xR is such that ax and bx, then cx. Prove that a and b have a least common multiple in R.

The existence of a greatest common divisor was shown in Lemma 3.7.1, where the ideal I(a,b)={ra+sbr,sR} was employed. We seek another natural ideal to consider. Clearly we want to look at elements of R which are multiples of both a and b. The multiples of a are the ideal (a)={rarR} while the multiples of b are the ideal (b)={rbrR}. The intersection of those ideals, J=(a)(b),

is again an ideal and its elements are exactly those which are divisible by both a and b. By Theorem 3.7.1, J is generated by some element lR and we claim that l is a least common multiple of a and b. As lJ, we have that al and bl. If xR is such that ax and bx, then xJ and so lx. Therefore we have exhibited a least common multiple of a and b.

Herstein 3.7.8: Let R be Euclidean and let a,bR. Denoting least common multiple by [a,b] and greatest common divisor by (a,b), show that [a,b](a,b)=ab.

By Theorem 3.7.2, we can express a=p1pmandb=q1qn

with the pi and qj prime elements of R. We can construct a greatest common divisor of a and b by iterating through the list P={pi} and picking out those primes which also appear in the list of Q={qj} (up to associates). Taking this subset P of the P and computing its product gives a ring element d, which will be a greatest common divisor. It is clear, because it is a product of primes which divide both a and b, that da and db. Furthermore, any other xR with xa and xb must have xd: suppose it were otherwise, then there would be a prime πR with πx, so therefore πa and πb, but π∤d. This contradicts the construction of d. Therefore d is a greatest common divisor of a and b.

Now that the list of P has been pared down somewhat, we can take a product over the remaining PP and over all of the Q, and call this product l. Because nothing has been removed from Q, we see that both al and bl: Q still contains all of the primes that were common to a and b, and PP retains whatever was left over from a after the culling. If x is another multiple of a and b, so ax and bx, then we must have lx: suppose it were otherwise, then there would be a prime πR with πl but not πx. Of course, every prime dividing l must divide one or both of a and b, so this would show that x could not be a common multiple. Therefore we must have lx and hence l is a least common multiple of a and b.

Finally, we have that dl=p1pmq1qn=ab

which is the desired result.

comments powered by Disqus