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:R\setminus 0\to {\mathbb{Z}}^{\ast }$ such that

  1. $d(a)\le d(ab)$ for $a,b\in R\setminus 0$.

  2. For $a,b\in R\setminus 0$, there exist $r,s\in R$ with $a=sb+r$ and either $r=0$ or $d(r)<d(b)$.

  Here, ${\mathbb{Z}}^{\ast }$ 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 $a\in R$ such that $I=(a)=\{ax\mid x\in R\}$. 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,b\in R$ with $a\mathrm{\ne }0$. $a$ divides $b$, or $a\mid b$, if there exists $c\in R$ with $b=ac$.

• Definition: Let $R$ be commutative and let $a,b,d\in R$ with $a,b\mathrm{\ne }0$. $d$ is a greatest common divisor of $a$ and $b$ if $d\mid a$ and $d\mid b$ and, if $c\mid a$ and $c\mid b$, then $c\mid d$.

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

• Definition: Let $R$ be commutative and unital. Element $a\in R$ is a unit if there exists $b\in R$ with $ab=1$.

• Lemma 3.7.2: Let $R$ be an integral domain and let $a,b\in R$ be such that $a\mid b$ and $b\mid a$. Then $a=ub$ for some unit $u\in R$.

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

• Lemma 3.7.3: Let $R$ be Euclidean and let $a,b\in R$. If $b\mathrm{\ne }0$ is not a unit, then $d(a)<d(ab)$.

• Definition: Let $R$ be Euclidean. A non-unit $\pi \in R$ is prime if, with $a,b\in R$, $\pi =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,b\in R$. $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,c\in R$ be such that $a\mid bc$ but $(a,b)=1$. Then $a\mid c$.

• Lemma 3.7.6: Let $R$ be Euclidean and let $a,b,\pi \in R$ with $\pi$ prime. If $\pi \mid ab$ then $\pi$ divides $a$ or $b$ or both.

• Theorem 3.7.2 (unique factorization): Let $R$ be Euclidean and let $a\in R$ 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 $a\sim b$ if $a$ is an associate of $b$ is an equivalence relation.

Let $r,s,t\in R$.

1. $\sim$ is reflexive: $r=r1$ so that $r\sim r$.

2. $\sim$ is symmetric: If $r\sim s$, then suppose $u\in R$ is the unit such that $r=su$. There exists $u^{\mathrm{\prime }}\in R$ with $u{u}^{\mathrm{\prime }}=1$, and multiplying by this $u^{\mathrm{\prime }}$ gives $s=r{u}^{\mathrm{\prime }}$ and therefore $s\sim r$.

3. $\sim$ is transitive: If $r\sim s$ and $s\sim t$, then there are units $u,v\in R$ with $r=su$ and $s=tv$. Of course, $r=t(uv)$ and, because $uv$ is a unit, $r\sim t$. $uv$ is a unit because there exists $u^{\mathrm{\prime }},v^{\mathrm{\prime }}\in R$ with $u{u}^{\mathrm{\prime }}=v{v}^{\mathrm{\prime }}=1$, and $(uv)(u^{\mathrm{\prime }}{v}^{\mathrm{\prime }})=1$.

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

Let $d_1$ and $d_2$ 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, $d_2$ must, as a divisor of $a$ and $b$, divide $d_1$. Then $d_1=d_{2}r$ for some $r\in R$. By the same token, there exists $s\in R$ such that $d_2=d_{1}s$. Then $d_1=d_{1}rs$, or $d_1(1-rs)=0$. We have $rs=1$ so that $r$ and $s$ are units, and therefore $d_1$ and $d_2$ are associates.

Alternately, we can appeal to Lemma 3.7.2.

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

If $a$ is a unit, then there exists $b\in R$ with $ab=1$. We have that $d(a)\le 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)\le 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,r\in R$ 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)\le 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,b\in R$. Prove that their greatest common divisor $(a,b)$ may be found by

$$\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 $r_{n-1}=q_n{r}_n$ 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, $r_n$, is in fact $(a,b)\mathrm{.}$

Stepping up the chain, we have that $$r_{n-2}=q_{n-1}{r}_{n-1}+r_n=(q_{n-1}{q}_n+1)r_n$$

so that $r_n\mid r_{n-2}$. Iterating this easily shows that $r_n\mid r_i$ for all $0<i<n$. Then also $$r_n\mid (q_1{r}_1+r_2)=a$$

and $$r_n\mid (q_{0}a+r_1)=b\mathrm{.}$$

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

If we can additionally prove that $r_n=\lambda a+\mu b$ for some $\lambda ,\mu \in R$, then we will be done. Why? If $c\in R$ is another divisor of both $a$ and $b$, then $c\mid \lambda a$ and $c\mid \mu b$ so that $c\mid r_n$. But this is actually easy to see. If we re-arrange each step of the algorithm, we find that $r_1=1b-q_{0}a$ and $r_2=a-q_1{r}_1=(1+q_0{q}_1)a-q_{1}b$, and so forth. Proceeding in this way, we can express every remainder as a linear combination of $a$ and $b$. Finally, we arrive at $$r_{n-2}=q_{n-1}{r}_{n-1}+r_n$$

which is at last rearranged into the form $r_n=\lambda a+\mu b$.

Notice that we are implicitly working in the ideal $I(a,b)=\{ra+sb\mid r,s\in R\}$. 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 $2\mid 4$ and $2\mid 8$. 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 $u\in I$ so there exists $v\in R$ such that $uv=1$. Let $r\in R$ be arbitrary. We have $u(vr)=(uv)r=r\in I$ so that $R\subset I$ 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 $1\in U(R)$. Letting $u\in U(R)$, we have $v\in R$ such that $uv=1$. This also means that $v\in U(R)$ and hence $U(R)$ contains inverses. Finally, we note that if $u_1,u_2\in U(R)$, then $u_1{u}_2$ is also a unit. There exist $v_1,v_2\in R$ such that $u_1{v}_1=1$ and $u_2{v}_2=1$. Then $u_1{u}_2{v}_1{v}_2=1$ so that $u_1{u}_2\in U(R)$ and the set is closed under multiplication.

Herstein 3.7.7: Let $R$ be Euclidean and let $a,b\in R$. A least common multiple of $a$ and $b$ is a number $c\in R$ such that (1) $a\mid c$ and $b\mid c$, and (2) if $x\in R$ is such that $a\mid x$ and $b\mid x$, then $c\mid x$. 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+sb\mid r,s\in R\}$ 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)=\{ra\mid r\in R\}$ while the multiples of $b$ are the ideal $(b)=\{rb\mid r\in R\}$. The intersection of those ideals, $$J=(a)\cap (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 $l\in R$ and we claim that $l$ is a least common multiple of $a$ and $b$. As $l\in J$, we have that $a\mid l$ and $b\mid l$. If $x\in R$ is such that $a\mid x$ and $b\mid x$, then $x\in J$ and so $l\mid x$. Therefore we have exhibited a least common multiple of $a$ and $b$.

Herstein 3.7.8: Let $R$ be Euclidean and let $a,b\in R$. 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=p_1\cdots p_m\mathrm{a}\mathrm{n}\mathrm{d}b=q_1\cdots q_n$$

with the $p_i$ and $q_j$ prime elements of $R$. We can construct a greatest common divisor of $a$ and $b$ by iterating through the list $P=\{p_i\}$ and picking out those primes which also appear in the list of $Q=\{q_j\}$ (up to associates). Taking this subset $P^{\mathrm{\prime }}$ 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 $d\mid a$ and $d\mid b$. Furthermore, any other $x\in R$ with $x\mid a$ and $x\mid b$ must have $x\mid d$: suppose it were otherwise, then there would be a prime $\pi \in R$ with $\pi \mid x$, so therefore $\pi \mid a$ and $\pi \mid b$, but $\pi \mid ̸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 $P\setminus P^{\mathrm{\prime }}$ and over all of the $Q$, and call this product $l$. Because nothing has been removed from $Q$, we see that both $a\mid l$ and $b\mid l$: $Q$ still contains all of the primes that were common to $a$ and $b$, and $P\setminus P^{\mathrm{\prime }}$ retains whatever was left over from $a$ after the culling. If $x$ is another multiple of $a$ and $b$, so $a\mid x$ and $b\mid x$, then we must have $l\mid x$: suppose it were otherwise, then there would be a prime $\pi \in R$ with $\pi \mid l$ but not $\pi \mid 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 $l\mid x$ and hence $l$ is a least common multiple of $a$ and $b$.

Finally, we have that $$dl=p_1\cdots p_m{q}_1\cdots q_n=ab$$

which is the desired result.