RING UNIT: FCIR

FACTORIZATION CONCEPTS FOR INTEGRAL RINGS

Developed by the Association for Conceptual Studies

Presented by: F Richard Singer III Edition Date 1/2009

Website: http://www.conceptualstudy.org

Note: For an MS Word Version of this file use the link Factorization Concepts.doc

Prerequisites: Basic concepts, such as those presented in the earlier unit Basic Group and Ring Laws. An ability to work with some simple examples of commutative rings including subrings of the complex numbers, cyclic rings (i.e the integers modulo n), polynomial rings.

Def: An integral ring R is a commutative ring having a multiplicative identity (denoted by 1) and having 0 as the only annihilator (or using more common terminology having no proper zero divisors).

Variables: Unless otherwise indicated;

i, j, k, m, n denote natural number

other ordinary lower case letters denote elements of the main ring being considered

and ordinary upper case letters denote subsets of that ring

lower case Greek letter elements of a ring containing the main ring being considered

Notation: A+B is the set obtained by adding each element of A to each element of B. aB is the set obtained by multiplying each element of B by a.

The Arial Black symbols N, Z, Q, Z_n denote the natural numbers, the integers, the rational numbers, the cyclic ring mod n. The Arial Black symbol i denotes Ö-1.

Note: We use the term ‘integral ring’, instead of ‘integral domain’, in order to stress that an integral domain is a type of ring. If ab = 0 then we call as an annihilator of b. By commutivity a is an annihilator of b implies that b is an annihilator of a. Annihilators other than 0 are usually called zero divisors.

Simple Ring Extensions: Let K be any integral ring, R any subring of K, k any element of K.
R[k] denotes the smallest subring of K containing R and k in the sense below.

1. R[k] is a subring of K & kÎR[k] & R Í R[k]

2. A is a ring & kÎA & R Í A Þ R[k] Í A

Example: The ring of gaussian integers Z[i] = {a+bi: a,bÎZ}. To check this denote the set Indicated as G. Clearly G is a subring of the complex numbers & iÎG & Z Í G, so part 1 is satisfied. To see that is satisfied let A be any ring of complex numbers with iÎA & Z Í A. Since rings are closed with respect to addition and multiplication m+niÎA for all m,nÎZ.

Example: The ring Z[Ö2] = {a+bÖ2: aÎZ & bÎZ}.

Example: The ring Z[/2] = {a2^x: xÎZ & a is odd} È {0}.

The Arial Black symbol x denotes an element that is transcendental over R, i.e x is an element in an ring extending R and x is not the root of any polynomial with coefficients in R. It the basic polynomial used to generate the ring R[x] of polynomial forms with coefficients in R.

Example: The ring Q[x] = {a₀+…+a_nxⁿ : a₀,…, a_nÎQ & nÎN}.

SECTION 0 SOME BASIC RESULTS AND NOTATION

Units: The Arial Black symbol U denotes the set of elements in some integral ring R that have multiplicative inverses in R. U is called is called the set of units in R.

Example: For instance, the set of units in Z is {1.-1}, the set of units in Z[i] is {1,-1,i,-i }, the set of units in Q is Q-{0}. the set of units in Z[/2] is {±2^k: kÎZ}.

Factors and Associates: The concept of a factor is crucial. We say that c is a factor of b (or that b is a multiple of a) iff b = cx for some xÎR. We write this as c½b. Since uÎU Û $x ux = 1 (namely for x = /u), the units can be thought of as the factors of 1. We say that c is an associate of b in R iff c½b & b½c. We write this as c » b. The associate class for an element b is the set of all elements that are associates of b. The associate class for 1 is U, since 1½u & u½1 Û uÎU.

Example: Each associate class in the ring of integers (except for {0}) has exactly two elements and these two elements are additive inverses of each other.

Remark: The proofs of the lemmas below are straightforward. If you have any doubts, write some of them in detail. These lemmas will be used as needed and without reference in this present unit.

Lm1: 1. a½a & 1½a 2. a½b & b½c Þ a½c 3. c ¹ 0 Þ (a½b Û ca½cb)

4. a½b Þ a½bc 5. bcïa Þ bïa 6. a½b & a½c Þ a½(bx+cy)

Notation: The symbol ‘¯’ will denotes the proper factor relation, i.e. c¯b iff c½b & Øbïc. Thus a¯a Û aïa & Øaïa, which is a contradiction proving Lm2.1. Since a¯b Û aïb & Øbïa, by Lm1.4 and Lm1.5 a¯b Þ aïbc & Øbcïa, which proves Lm2.2.

Lm2: 1. Øa¯a 2. a¯b Þ a¯bc 3. a¯b & b½c Þ a¯c

Remark: Lm3.2 says that associates have the same factors and are factors of the same elements.

Lm3: 1. » is an equivalence relation 2. a » b Û $u (uÎU & a = ub)

3. a » b Þ (c½a Û c½b) & (a½c Û b½c) 4. c ¹ 0 Þ (a » b Û ac » bc) 4

Lm4:. aÎU is equivalent to each of he following

a » 1, "b a½b , Ø$b b¯a, $u(uÎU & a » u), $u(uÎU & a½u), $u(uÎU & Øu¯a)

Primes and Composites in R: s is a significant factor of b iff s½b & Ø s » b & sÏU.

P = {p: pÏU & p has no significant factors)} C = {c: c ¹ 0& c has a significant factor}

These sets are called P primes, C composites in R.

gÎGCF{a,b} iff g½a & g½b & "d(d½a & d½b Þ d½g) greatest common factors

Lm5: 1. pÎP Û pÏU & "c(c¯p & cÎU)

2. pÎP Û "a"b(ab = p Þ (aÎU & b » p) Ú (bÎU & a » p)

3. cÎC Û $a(a¯c & aÏU) & c ¹ 0.

4. Exactly one of the following: a = 0, aÎU, aÎP, aÎC

Lm6: 1. gÎGCF(a,b) & dÎGCF(a,b) Þ g » d

Morphisms: A function  for a ring R onto a ring S is a morphism from R onto S iff

Â(a+b) = Âa+Âb Â(a·b) = Âa·Âb

Prop: If  is a morphism from R onto S then Â0 = 0 & Â1 = 1 & Â(-a) = -Âa.

Note To show Â1 = 1, note that Â(0+0) = Â0+Â0, and hence Â0 = Â0+Â0, giving Â0 = 0.

Example: Let Â_n be the function that maps an integer to its remainder mod n. This function is a morphism form Z to Z_n.

Kernel: The kernel of a morphism Â:R®S is the set of elements in R that it maps to 0.

Prop: If K is the kernel of a morphism Â:R®S then K is closed with respect to addition and the product of any element of R with an element of K is an element of K.

Note: The above proposition says that the kernel of a morphism is an ideal in the sense of the definition below. It can also be shown that the any ideal J in a ring R is the kernel of some morphism from R to some ring S. Moreover if J is the kernel of a morphism from R onto a ring S and also the kernel of a morphism from R onto a ring T then S and T are isomorphic. Altho these results are not used in this unit, they will be discussed in an appendix.

Ideals: J is an ideal in a ring R iff a,bÎJ Þ a+bÎJ & cJ Í J i.e. J is closed with respect to addition. It should also be noted that since a-b = a+-b an ideal is closed with respect to subtraction.

An ideal is a maximal ideal iff it is a proper subset of no other ideal except R.

An ideal J is a prime ideal iff abÎJ Þ aÎJ Ú bÎJ

For example, the even integers form an ideal in the ring of integers. It is also both a prime ideal and a maximal ideal in Z. Likewise for any prime p the multiples of p form an ideal in Z which is also both a prime ideal and a maximal ideal in Z, as we shall later prove.

Activity: Prove Th 1 and Th2 below.

Th1: 1. aR is an ideal in R 2. a½b Û bR Í aR 3. a¯b Û bR Ì aR

Th2: I and J are ideals in R Þ I Ç J and I+J are ideals in R

Th3: J is a maximal ideal in R Þ J is a prime ideal in R

Prf (main idea): Let J be maximal in R. To show that J is a prime ideal, show abÎJ & aÏJ Þ bÎJ. Assuming abÎJ & aÏJ, since is maximal, aR+J = R. Thus 1 = ac+j for some cÎR and some jÎJ. This gives b = abc+bjÎJ.

Th4: Let  be a ring morphism from R to S with kernel K

1. S is a field ring Û K is a maximal ideal 2. S is an integral ring Û K is a prime ideal

Prf1 (main idea): Assume S is a field. Let J be an ideal with K Ì J. Let yÎJ-K. Since Ây ¹ 0, there is some xÎR with Âx·Ây = 1, so Â(1-xy) = 0, 1-xyÎK. Thus 1 = (1-xy)+xyÎJ and hence K is a maximal ideal. Now assume K is a maximal ideal in R. Chose any sÎS with s ¹ 0. S = Âx for some x in R-K. 1ÎxR+K, and so 1 = xy+k, 1 = Âx·Âk. Thus s·Ây = 1.

Prf1 (main idea): Assume S is an integral ring. Let xyÎK. Since Âx·Ây = 0, Âx = 0 Ú Ây = 0.
Assume K is a prime ideal. Let ab = 0 for some a,bÎS. Let a = Âx & b = Ây. Thus Â(xy) = 0. So xyÎK, etc.

Activity: Write a detailed proofs for Th3 and Th4.

SECTION 1 FACTORIZATION FOR INTEGERS

Perspective: Since all rational numbers (except 0) have multiplicative inverses that are rational number, for any bÎQ and any dÎQ (as long as d ¹ 0) we can define b divided by d as the rational number b·/d. Unlike the rational number, only 1 and ^-1 have multiplicative inverses that are integers. However b/d is an integer if d½b in Z. In general, it is the factorization properties of Z that are essential to the algebra of Z. Consider the example below.

Example: Since x²+4x-21 = 0 is equivalent to x(x+4) = 3·7 the equation has 3 as a natural number root. This equation is also equivalent to x(x+4) = -7·-3 giving -7 as an integer root. Since 3·7 and ^-7·^-3 are only ways to factor 21 with factors that differ by 4, these are the only roots. On the other hand, the equation x²+5x-21 = 0, is equivalent to x(x+5) = 21, which has no roots since 21 is not a product of factors that differ by 5. In general, since x²+yx-21 = 0 Û x(x+y) = 21. This equation has integer roots for x iff yÎ{20, 4, ^-4, ^-20}. Adopting another perspective, we can consider x²+yx-21 = 0 as a quadratic in two unknowns, and deduce its 8 root pairs {[20,1],[20, ^-21],…}. This can be extended to show that the number of root pairs [x,y] for an equation of the form x²+yx-b = 0 depends on number of ways b can be factored as a product of two integers.

Remark: Of course x²+4x-21 = 0 Û (x-3)(x+7) = 0, also yielding the roots indicated above and since Z is an integral ring, this also show that these are the only roots. The quadratic formula also gives these roots. You might consider if factoring equations whose right side is 0 or using the quadratic formula could be applied to obtain the other results indicated in the example above.

Division in Z and N: Even when an integer d is not a factor of an integer b we can divide and obtain a quotient and a remainder that are integers. Moreover the remainder is simpler than the divisor in the sense of being close to 0. For a natural numbers this is something we study in elementary school. This easily expands to negative integers. To divide a positive integer like 36 by a negative integer like ^-7 we can divide by 7 and take the additive inverse of its quotient. This works because 36 = 5·7+1 Û 36 = ^-5·^-7+1, i.e. dividing 36 by ^-7 gives a quotient of ^-5 and a remainder of 1. To divide ^-36 by 7 we can use 36 = 5·7+1 Û ^-36 = ^-5·7+^-1 i.e. we have a quotient of ^-5 and a remainder of ^-1 which is closer to 0 than 7. If we prefer a positive remainder, adding ^-7+7 we have ^-36 = ^-6·7+6. Unlike division for natural number, if we merely require that the remainder to be close to 0 than the divisor (as in the theorem below), remainders will not be unique (except for a remainder of 0). The proof below uses the fact that the distance of between any rational and at least one integer is less than 1. There are a number of proofs for this theorem that do not involve the relation between integers and rational numbers.

Division Th: "b"d$q$r(b = qd+r & |r| < |d|); where d denotes an integer other that 0.

Prf: Chose an integer q so |b/d-q| < 1 and let r = b-qd. So b = qd+r. Moreover |r| < |d| as can be seen from Multiplying |b/d-q| < 1 by |d|.

Uniqueness: Note that there are two choices of q such that |37/10-q| < 1;el q = 3 Ú q = 4. Thus using that analysis above we can write 37 = 3·10+7 or 37 = 4·10+^-3. Calling q the quotient and r the remainder when we divide 37 by ^-10 we obtain quotient ^-3 and remainder 7 or we could divide 37 by ^-10 obtaining quotient ^-4 and remainder ^-3. To obtain a unique quotient and remainder, we can specify that the remainder must be a natural number.

Division Th: "b"d$!q$!r(b = qd+r & 0 £ r < |d|) Note: $! means there is exactly one.

To show uniqueness. To show this assume (b = qd+r & r < |d|) & (b = pd+s & s < |d|), where variables denote elements of N. Then r-s = (p-q)d, and so d½r-s. Since we also have -d < r-s < d and since 0 is the only multiple of d between -d and d, we have r = s, and hence q = p.

Ideal in Z: In any ring R an ideal of the form aR is called a principal ideal in R. We will show that all of the ideals in Z are principal ideals. In other words, an ideal J in Z consists of the multiples of some integer n, and in fact some natural number n. Since the kernel of a morphism must be an ideal, this essentially determines the rings that are images of Z under a morphism. Specifically these images consist of all the finite cyclic rings, along with Z itself and the trivial ring {0}. See the appendix for a discussion of this.

Principal Ideal Th: If J is an ideal in Z the J = dZ for some dÎN.

Prf (main idea): Let d be the smallest positive integer in J. Let bÎJ and show bÎdZ; i.e. b = qd for some q. This suggest using the Division Th, b = qd+r & 0 £ r < d for some q and some r. We can show r = 0 by solving for r and showing that rÎJ.

Notation: Since the integers have only 1 and ^-1 as units, each associate class other than {0} has two elements, one of which is positive and one of which is negative. In particular for any a and b ,

Significance of Ideals: Not only are ideals significant in relation to morphisms, they relate to various factorization concepts. That every ideal in Z is principal can be used to prove that the greatest common factor of a and b is the sum of a multiple of a and a multiple of b. This can the be used to prove that if a prime divides a product then it divides at least one of the factors. There are integral rings such as Z[Ö5], in which these results do not hold. See Exercise ??.

Notation: gcf{a,b} denotes the positive element of GCF{a,b}

GCF Linear Combination Th: $x$y gcf{a,b} = ax+by

Prf (main idea): Consider the set J = {ax+by: x,yÎZ}. Show that J is an ideal of the form gZ with g >0, and hence $x$y g = ax+by,. Show that g½a & g½b & "d(d½a & d½b Þ d½g), and so g = s.

Prime Factor Th: pÎP & p½ab Þ p½a Ú p½b Note: pÎP is brief for p is prime in Z.

Prf (main idea): Assume pÎP & p½ab & Øp½a and show p½b. First show 1 = gcf{p,a}. Then use the linear combination Th to obtain b = abx+pby.

Cor: p, p₁,…, p_nÎP & p½p₁·…·p_n Þ p » p₁ Ú … Ú p » p_n

Cor: p, qÎP & p > 0 & q > 0 & p½qx Þ p = q Ú p½x

Activity: Write a detailed proofs for the above results.

Prime Factorization: Let p₁,…,p₂ be the positive prime factors of some integer g, where g ¹0. A positive prime power factorization set for g is a set of positive prime powers that satisfies the condition below for some unit u.

Note: Exponent whose values are 1 are understood rather than being written.

Example: {2², 3} is a positive prime power factorization set for 18. By the above Cor, if p is a positive prime and p½2·2·3 then p = 2 Ú p = 3; and so a positive prime power factorization set for 18 must be of the form {2^k,3^j}. Suppose 2^k·3^j = 18 = 2²·3. By cancellation we obtain 2^k·3^j-1 = 2². Since 3 is not a factor of 2², j = 1 and hence k = 2. Thus {2², 3} is the only positive power prime factorization set for 18. This illustrates the main ideas for proving the following theorem. See Exercise 2 for a more general illustration of these ideas.

Prime Factorization Th: Every composite g has a unique positive prime factorization set.

EXERCISES AND PROBLEMS

Ex1a: Let R = A[x], where A is the field of algebraic numbers. Describe U, P, C

Ex1b: Show Z[/8] = Z[/2]. Show that Z[/2][/3] = Z[/6]. Show that Z[/6]ÇZ[/10] = Z[/2]. Generalize each of the above.

Ex1c: Let R = Z[Ö2]. Show that 3+Ö2ÎU. Find at least 5 elements from each of U and P and C.

Ex1d: Describe the elements of each of the rings below and determine which are units.

Z, Z[i], Z[3i], Z[(1+Ö3i)/2], Z[/2], Z[/3], Z[/5], Z[/6], Z[/10]

In which of them does 10ÎU? In which of the above rings does 10ÎP? In which of the above rings does 10ÎC? In which of the above rings is 10 » 20? Classify 20 as U, P, C for each of these rings.

Ex2a: Show that 15ZÇ35Z = 105Z. Generalize.

Ex2b: Let R = Z[x]. Let ¶ denote ‘the degree of’. Using facts about Z and about degrees, show that fÎU Þ ¶f = 0. Then show that U = {1,^-1}. Show that if p is prime in Z the p then pÎP. Show that m,nÎZ Þ (mx+nÎP Û 1ÎGCF{m,n}. Show that Ø($g,h) 1 = 2g+xh. Use these results to show Ø($f) fR = 2R+xR, i.e. 2R+xR is not a principal ideal. Find an infinite collection of maximal ideal that are not principal ideals. Find ideals that are not prime and not principal.

Ex2c: Let R = Z[i] . Describe U. Which of 2,3,5,7,11,13 are prime in R? Let J = (1+i)R. For integers m and n, indicate which elements m+ni are in J. Show that J is maximal. Using J as the kernel of a ring morphism, what is the image of this morphism?

Ex2d: Let R = Z[3i] and J = {c:c = j+3ki & k = j (mod2)}, show that J is an ideal in R. Show that
J = (1+3i)R+2R. Show that J is not a principal ideal.

Ex3: Use The GCF Linear Combination Th to show that $x$y ax+by = c Û GCF{a,b}½c; i.e. an equation ax+by = c has an integer root pair [x.y] iff GCF{a,b} is a factor of c.

Ex4a: Explain why {a+bÖ5: a,bÎZ} is an integral ring. Explain why it is the ring Z[Ö5]. Show that the function ¢ defined by ¢(a+bÖ5) = a-bÖ5 is an automorphism Z[Ö5]. Note an automorphism is a one to one morphism from a set onto itself.

Ex4b: It can be shown that 2 is prime in Z[Ö5]. Find (a+bÖ5) and (c+dÖ5) from Z[Ö5] such that 2½(a+bÖ5)(c+dÖ5) & Ø2½a+bÖ5 & Ø2½c+dÖ5.

Ex4c: Use Exercise 1a to show that if a+bÖ5½2 then a-bÖ5½2, and hence a²-5b²½4. Now suppose 2 is not prime. Explain why this implies that 2 has a significant factor a+bÖ5½2 where a²-5b² = ± 2. Use a remainder morphism to obtain a contradiction.

Ac5: Consider the principal ideals in Z. Suppose we take the sum of 2 such ideals, say 15Z+35Z. Since 15Î5Z & 35Î5Z, 15Z Í 5Z & 35Z Í 5Z. Hence 15Z+35Z Í 5Z. Show 5Z Í 15Z+35Z , and so this ideal is the same as 5Z. What general result is suggested?

Ex6: The product {p^k,q^j} is a positive prime factorization set for a positive integer c. Explain why p and q are the only positive prime factors of c, and so a positive prime factorization set for c must be of the form {p^m,qⁿ}. Show that p^k·q^j = p^m·qⁿ with j ¹ n gives a contradiction.

Problem 1a: For N if d ¹0 , "b"d$!q$!r(b = qd+r & 0 £ r < d), where b,d,q,rÎN. Prove this with using the division theorem for integers. Hint, any rational number b/d is between two consecutive integers q and q+1 in the sense that q £ b/d < q+1. We can prove the division theorem for natural numbers without using anything about rational numbers. By the Archimedian principle some positive multiple of d is greater than b. By well ordering there is a least such multiple md. Take q as 1 less than m and r as b-qd. Give this proof in more detail.

Problem 1b: The division theorem for N also follows from the uniqueness version of the division theorem for Z. To see this note Since N Ì Z, and hence "b"d$!q$!r(b = qd+r & 0 £ r < |d|), where b,d,rÎN & qÎZ. Since d > 0, |d| = d. Furthermore, since b = qd+r & 0 £ r < d, q ³ 0. However the division theorem for N is in a sense more basic than the uniqueness version of the division theorem for Z. Use the division theorem for N to prove uniqueness version of the division theorem for Z. Hint, generalize the remarks made in the earlier discussion of division for Z and N.

Problem 1c: As an alternative we can obtain uniqueness of remainders in terms of absolute values by using remainders are closest to 0. For d = 5 then the remainders are {^-2, ^-1, 0, 1 ,2}. If you are interested you might want to proves that d odd Þ $!q$!r(b = qd+r & |r| < |d/2|). Hint, use the fact that if d is odd then there is an integer q with q-½ < b/d < q+½.

SECTION 2 FACTORIZATION FOR RATIONAL POLYNOMIALS

Perspective: Q[x] is the ring of polynomial with coefficients in Q. The degree of a polynomial f is denoted as ¶f. It is easy to show (see proof below) that Q[x] is an integral ring whose units are the elements of Q other than 0. As in any integral ring, f/d is in Q[x] if d½f in Q[x]. Moreover like Z, we have a division theorem which says that if d is not the zero polynomial we can divide any polynomial f by d and obtain a quotient q and a remainder r in Q[x] such that f = qd+r & ¶r < ¶d.

With the integers, we used absolute values to indicate that the remainder is simpler than the divisor. For polynomials we can use degrees to indicate that the remainder is simpler than the divisor. As with Z, this division theorem can be use to prove principal ideal, GCF linear combination, prime factor, prime factorization theorems.

Notation: In this section the letters a, b, c (with or without subscripts) denote rational numbers. The letters d, f, g, h and p, q,…,z denote polynomials.

Def: If f = c₀+c₁x+…+c_nxⁿ, where these coefficients are in Q and where c_n ¹ 0 then c_nxⁿ is called the leading term of f and c_n is called the leading coefficient of f and n is called the degree of f. Altho this defines the degree of non-zero elements of Q as 0, it does not define the degree of 0. We define the ¶0 as -¥ and specify -¥+n = -¥. This avoids adding special conditions on the main proposition about degrees given below.

Prop: 1. ¶(f·g) = ¶f+¶g 2. ¶f < ¶g Þ ¶(f+g) = ¶g 3. ¶f = ¶g Þ ¶(f+g) £ ¶g

Prf1: Let f = c₀+c₁x+…+c_nxⁿ and g = b₀+b₁x+…+b_mx^m. The leading term of fg is c_nb_mx^m+n. Since Q is an integral ring, the leading coefficient of fg is not 0.

Activity: Discuss how to prove parts 2 and 3. How might we have ¶f = ¶g Þ ¶(f+g) < ¶g?

Cor: Q[x] is an integral ring whose units are the units of Q.

Activity: Explain how the Cor follows from the proposition.

Remark: The above results generalize to R[x] for any integral ring R. For instance, Z[x] is an integral ring whose units are 1 and ^-1.

Remark: A monic polynomial is one whose leading coefficient is 1. Since the non-zero rational numbers are the units in Q[x], an associate class other than {0} consists of the rational multiples of some monic polynomial. The monic element of GCF{f,g} is denoted as gcf{f,g}.

Example: Before giving a proof of the division theorem for Q[x], we consider an example. Let
d = x²+2 and g = 2x⁵-7x. We can carry out division much as we do in ordinary algebra. Noting that 2x³·d = 2x⁵+4x³ has the same leading coefficient as g, we can write g as a multiple of d plus a polynomial whose degree is less than g.

g = 2x⁵-7x = (2x⁵+4x³)-4x ³-7x = 2x³·d+(^-4x ³-7x)

We can then apply the same idea to write ^-4x³-7x as ^-4x·(x²+2)+x = ^-4x·d+x. This gives g as a multiple of d plus a polynomial of even smaller degree.

g = 2x³·d+(^-4x³-7x) = 2x³·d+^-4x·d+x. = (2x³-4x)·d+x

This gives the desired result, but had it not we could repeat the process. In general any polynomial g whose degree is not less the degree of d can be written as a multiple of d plus a polynomial of smaller degree than ¶g.

Remark You can view the idea in the example as repeated use of the next lemma.

Lm: Let g = c₀+…+c_n-1x^n-1+c_nxⁿ and d = a₀+…+a_k-1x^k-1+a_kx^k where n ³ k & c_n ¹ 0 & a_k ¹ 0

$f$h(g = fd+h & ¶h < ¶g)

Prf Let f = cx^n-k where c = c_n/a_k. Let h = g-fd, which gives g = fd+h. Moreover ¶h < ¶g since,

h = (c₀+…+c_n-1x^n-1+c_nxⁿ)-(ca₀x^n-k+…+ca_k-1x^n-1+c_nxⁿ) = (c₀+…+c_n-1x^n-1)-(ca₀x^n-k+…+ca_k-1x^n-1)

Division Th d ¹ 0 Þ $q$r(g = qd+r & ¶r < ¶d)

Prf (main idea): Use mathematical induction on the degree of g. If ¶g < ¶d then let q = 0 and r = g. Assume that the hold for all polynomial h of degree less than the ¶g and use the above lemma.

Activity: Write a detailed proof of the Division Theorem.

Division Th (uniqueness) $!q,$!r(g = qd+r & ¶r < ¶d) ; where d ¹ 0.

Prf: Assume (g = qd+r & ¶r < ¶d) & (g = pd+s & ¶s < ¶d). Then (q-p)d = s-r. Since ¶(s-r) < ¶d,. and ¶(s-r) = ¶d+¶(q-p), s-r = 0 & q-p = 0. This gives q = p & r = s.

Remark: You might note that a difference in the uniqueness result. In Q[x] we get uniqueness using ¶ to measure simplicity. In Z we cannot use absolute value of remainder if we want to have uniqueness.

Generalization: There is nothing in the Division Theorem for Q[x] that depends on any properties of Q except the field laws. Thus we have can give the same proof for the following theorem.

Division Th (for R[x] where R is any field) d ¹ 0 Þ $!q$!r(g = qd+r & ¶r < ¶d)

Principal Ideal Th: If J is an ideal in Q[x] the J = dQ[x] for some monic polynomial.

Prf (main idea): Let n be the smallest positive integer which is the degree of some element in J. Let d be a monic polynomial in J of degree n. Let bÎJ and show bÎdZ; i.e. b = qd for some q. This suggest using the Division Th, b = qd+r & ¶r < ¶d for some q and some r. We can show r = 0 by solving for r and showing that rÎJ.

GCF Linear Combination TH: $x$y gcf{f,g} = fx+gy

Prf (main idea): Consider the set J = {fx+gy: x,yÎZ}. Show that J is an ideal of the form sZ, and hence $x$y s = fx+gy,. Show that s½f & s½g & "d(d½f & d½g Þ d½s), and so gcf{f,g} = s.

Prime Factor Th: pÎP & p½fg Þ p½f Ú p½g Note: pÎP is brief for p is prime in Q[x].

Prf (main idea): Assume pÎP & p½fg & Øp½f and show p½g. First show 1ÎGCF{p,f}. Then use the GCF Linear Combination Th to obtain g = fgx+pgy.

Cor: p, p₁,…, p_nÎP & p½p₁·…·p_n Þ p » p₁ Ú … Ú p » p_n

Cor: p, qÎP & p > 0 & q > 0 & p½qf Þ p = q Ú p½f

Prime Factorization: Let p₁,…,p₂ be the positive monic factors of some polynomial g, where g ¹0. A monic prime power factorization set for g is a set of monic prime powers that satisfies the conditions below for some unit u.

Prime Factorization Th: Every composite f has a unique monic prime factorization set.

EXERCISES AND PROBLEMS

Ex1: In all parts of Exercise 1, F is a subfield of an integral ring R and cÎR. The substitution functions ŝ_c:F[x]®R are the function which substitutes c for x. Thus for f = a₀+a₁x+…+a_nxⁿ we have ŝ_cf = a₀+a₁c+…+a_ncⁿ. Explain why (or actually prove) that ŝ_c is a ring morphism. When c is understood form context we abbreviate ŝ_c as ŝ.

Ex1b: Consider ŝ₀:Q[x]®Q and ŝ₁:Q[x]®Q. Express the kernel K of these morphisms as a principal ideal in Q[x]. Show that these kernel are maximal ideals in Q[x]. Generalize.

Ex1c: Consider ŝ:Q[x]®Q[x] that substitutes x+1 for x in every polynomial. What is the kernel K of this morphism? Explain why ŝ is an isomorphism, i.e. both one to one and onto.

Ex1d: Consider ŝ:Q[x]®Q[x] that substitutes x² for x in every polynomial. What is the kernel K of ŝ? Explain why ŝ is a monomorphism but not an isomorphism, i.e. it is one to one but not onto.

Ex1e: Consider ŝ:Q[x]®Q[Ö2] that substitutes Ö2 for x in every polynomial. Express the kernel K of this morphism as a principal ideal in Q[x]. Explain why ŝ is a epimorphism but not a monomorphism, i.e. it is onto be not one to one.

Ex1f: Consider ŝ₁: Z₂[x] ®Z₂. Express the kernel K of ŝ as a principal ideal in Z₂[x]. Use this morphism with the Division Theorem to show that gÎK Û g has an even number of terms’. Hint by Th1, g = q(x+1)+r where rÎ{0,1}. Thus ŝg = ŝq·(1+1)+r = r. Furthermore since the terms of g are powers of x, ŝ applied to any term of g is 1. Thus the sum of these terms is the number of these terms modulo 2, giving r = 0 if and only if the number of these terms is even.

SECTION 3 SOME EUCLIDEAN RINGS

Perspective: The previous sections showed that Z and Q[x] satisfy a Division Theorem that says that we can divide by any non-zero element d of R and obtain a quotient and a remainder, where the remainder is in some sense simpler that d. We also generalized the results about Q[x] to F[x] for any field F. The significance of showing this was that it enabled us to show that all the ideals in these rings are principal and to derive the factorization properties of these rings in relation to primes. Roughly speaking an integral ring for which there is a Division Theorem is called an euclidean ring, and any such ring all ideal will be principal ideals and the prime factorization properties. Some other rings that can be shown to be euclidean include Z[i] and Z[/2] and Z[Ö2]. To make this concept of an euclidean ring precise, we need to specify our simpler than concept.

Simplicity Functions: A morphic simplicity function is a function $ from R to N such that:

$(a·b) = $a·$b $a = 0 Û a = 0 $a = 1 Û aÎU

For Q and Z, we used $a = |a|, which clearly satisfies these conditions. For Q[i] and Z[i] we use the square of the distance from 0, namely $(x+yi) = x²+y², where x,yÎQ. For Q[Ö2] and Z[Ö2]we use $(x+yÖ2) = |x²-2y²|, where x,yÎZ. For Z[/2] we define $0 = 0 and $(2^km) as |m| if m is odd. In proving the Division Theorem for Q[x] which used ¶, but ¶(fg) ¹ ¶f¶g. However for any field F, we define a simplicity function for F[x] by letting $0 = 0 and $f = 2^¶f. Sinnce ¶r < ¶d Û $r <$d; the Division Theorem for F[x] can also be stated in terms a morphic simplicity function.

Activity: Check that the functions described above are morphic simplicity functions.

Euclidean Rings: An integral ring R is an ER i.e. an euclidean ring iff there is a morphic simplicity function $ that satisfies the Division Theorem condition below.

"b"d(d ¹ 0 Þ $q$r(b = qd+r & $r < $d))

We call q a quotient and r its remainder from dividing b by d.

Activity: Explain why bÎQ[i] Þ $q$a(qÎZ[i] & b = q+a & $a < 1). Hint picture the complex plane.

Activity Show that bÎQ[Ö2] Þ $q$r$t (b = q+a& $a < 1). Hint let b = u+vÖs where u,vÎQ. Let r Let a = (u-m)+(v-n)Ö2 where m is the closest integer to u and where n is the closest integer to v. Note that (u-m)² £ ¼ and 2(v-n)² £ ½ show $a < 1.

Th1 With $ as defined above, the rings Z, F[x], Z[i], Z[/2], Z[/3], Z[Ö2], Z[Ö3] are euclidean.

Prf for Z, F[x]: Previous sections.

Prf for Z[i]: Since b/dÎQ[i], ($qÎZ[i])($aÎQ[i])(b/d = q+a & $a < 1). Since b = qd+ad, letting r = ad gives b = qd+r & $r = $a$d < $d. Since r = b-qd, rÎZ[i].

Prf for Z[/2]: Let d = 2^km, where k,mÎZ & m is odd. If b = 0 let q = r = 0. Otherwise b = 2^jn where j,nÎZ & n is odd. Using Th1 for Z, we can choose u,vÎZ with n = um+v & |v| < |m|. Multiplying by 2^j gives b = u2^j-kd+2^jv. Let q = u2^j-k & r = 2^jv. Thus $r = $v £ |v| < |m| = $m.
For more detail, note that v is of the form 2^ts where s is odd and |s| £ |v|. Thus $v £ |v|.

Prf for Z[Ö2]: By Exercise 9, $b$r$t (a/d = b+(r+tÖ2)) & | r | £ ½ & | t | £ ½. Multiplying by d gives $b$u$v (a = bd+(r+tÖ2)d). Since (r+tÖ2)d = a - bdÎR, let g denote (r+tÖ2)d. Furthermore Hence ||g|| = | r²-2t² |·||d|| < ||d||.

Exercises and Problems

Ex1: Let $ be a simplicity function for R. Show that a¦b Þ 1 < $a < $b.
Show that bÎC Þ $b is composite in N.

Ex2: Prove Th1 for Z[/3] and for Z[/6].

Problem: Prove Th1 for Z[Ö3] and for Z[1/2+Ö5/2].

Problem: Does Th1 hold for every ring R such that Z Í R Í Q? Why or why not?

SECTION 4 PRINCIPAL IDEAL RINGS

Def: An ideal J is principal if it is of the form gR, in which case g is said to generate J. R is a PIR (principal ideal rings) iff all ideal in R are principal.

Perspective: Section 1 showed that all ideals in Z are principal. For Z, each such ideal is the kernel of a morphism from Z to Z_k. This gives all of the possible morphic images of Z. Likewise Section 2 showed that all ideals in Q[x] are principal. As will be indicated in Th2, every ER is a PIR, by merely using the essentially the same proofs as in Section 1 and Section 2. Thus all ideals in Z[i] are principal , as well as a all ideal in number of rings between Z and Q, and also in Z[Ö2]. However but it is not difficult to find integral domains having ideals that are not principal. See exercises for this section.

Th2: Every Euclidean Ring is a Principal Ideal Ring.

prf: We must show that for each ideal J there is a s with J = sR. Clear if J ={0}. Otherwise, by the well ordering of N, chose a least s in J, i.e. an s such that (#) holds.

(#) sÎJ & "c(cÎJ & c ¹ 0 Þ 0 < $s £ $c)

Clearly sR Í J. Suppose dÎJ and chose q and r so d = qs+r & $r < $s. Since r = d-qs, rÎJ. Thus by (^#) and the fact that $ is a simplicity function r = 0. Thus d = sqÎsR. So J Í sR.

Remark: In the rest of this section, R denotes any PIR. The results are basically the same as those for Z and Q[x], except for a minor complication. In Z we selected the positive element of an associate class to represent the class. Likewise in Q[x] we selected the monic element of an associate class to represent the class. In the general case there may not be an obvious way to select a special representative. Thus we will state results in term of any member of a class rather than in terms of some special representative. We also state some result that we omitted earlier.

Th3: cÎGCF{a,b} Þ aR+bR = cR & ($x,y) c = ax+by

prf1: Assume cÎGCF{a,b}. Clearly aR+bR Í cR. Since R is a PIR, so $d aR+bR = dR. Thus d is a common factor of {a,b} and so d½c. Thus cR Í dR = aR+bR. This gives ($x,y) c = ax+by

Cor: GCF{a,b} = U & a½c & b½c Þ ab½c

prf: ($x,y) ax+by = 1. Thus acx+bcy = c. Now use b½c Þ ab½ac and a½c Þ ab½bc.

Th4: 1. GCF{a,b} = U & a½bc Þ a½c 3. pÎP & p½a₁·...·a_n Þ p½a₁ Ú ... Ú p½a_n

2. pÎP & p½bc Þ p½b Ú p½c 4. p,p₁,...,p_nÎP & p½p₁·...·p_n Þ p » p₁ Ú ... Ú p » p_n

prf1: Assume GCF{a,b} = U & a½bc. Since 1ÎGCF{a,b}. ($x,y) ax+by = 1. Multiplying by c give acx+bcy = c. Since a½bc, we have a½c.

prf2: Assume pÎP & p½ab & Øp½a. Since GCF(a,p) = U, by part 1, p½b.

prf3,4: Follows from part 2.

Th5: 1. $p(pÎP & J = pR) Û J is a prime ideal 2. J is a maximal ideal Û J is a prime ideal

prf1: Suppose $p(pÎP & J = pR). If abÎJ then p½ab and by Th4 p½a Ú p½b, so aÎJ Ú b½J. Thus J is a prime ideal. Conversely suppose J is a prime ideal. Since R is a PIR, J = pR for some p. If p was not prime then p = ab for some pair of proper factors {a,b}. So p½ab & Øp½a & Øp½b.

prf2: We already know that in any ring J is a maximal ideal Þ J is a prime ideal. Suppose that J is a prime ideal. Choose a prime p so J = pR. Suppose pR Ì bR for some b. This gives bp. So bÎU. Thus pR is maximal.

Cor: Â morphism: R®S Þ S is a field Ú S has non-zero annihilators

Notation: Recall that c is a significant factor of b iff c½b & Ø c » b & cÏU. Since there is no notation for significant factor, we temporally use c¦b for c is a significant factor of b.

Note: By the well ordering principle, Th6 part 2 is trivial for Z and for Q[x]. Part 1 then follows from part 2. However we??

Th6: 1. Any strictly ascending chain of ideals is finite.

2. Any descending chain of significant factors is finite.

prf1: Suppose there was an infinite ascending chain of ideals. Since R is a PIR the chain is of the form c₁R Ì c₂R Ì c₃R ... Let J = {x: ($m) xÎc_mR}. It is easy to show that J is an ideal, so J = cR for some c. ("n) c_nR Í cR. Since cÎJ, ($m) cÎc_mR, giving J = c_mR. It follows that c_m+1R Í c_mR, This contradicts c_mR Ì c_m+1R.

prf2: Consider there was an infinite descending chain of factors ... c₄¦c₃¦c₂¦c₁. From this we can form an infinite the ascending chain c₁R Ì c₂R Ì c₃R ... Apply part 1.

Lm: cÎP Ú cÎC Þ $p(pÎP & p½c).

prf: Trivial if cÎP. Let c be a composite. Let c₁¦c. If c₁ÎP we are done. If not let c₂¦c₁. If c₂ÎP we are done. Etc. By Th6, this process must terminate, giving c_n prime for some n.

Terminology: If c = u·p₁·...·p_n where uÎU and p₁,…p_nÎP then this factorization u·p₁·...·p_n is called a prime factorization of c. When u = 1, it will be omitted. For instance, 2·2·2·3·(^-3) is a prime factorizations of ^-72 in Z. One reason for allowing units in a prime factorization is so we can write a prime factorization so different primes from the same associate class do not appear in the factorization. We call such a factorization regular. So we can use ^-1·2·2·2·3·3 as a regular prime factorization of ^-72, and write this as -1·2³·3².

Th7: cÎP Ú cÎC Þ c has a prime factorization.

prf: By the lemma we can choose p₁ so p₁½c₁. So c₁ = p₁·c₂ for some c₂. If c₂ÏU, choose p₂ so p₂½c₂ and let c₂ = p₂·c₃. This gives c = p₁·p₂·c₃. Etc. Since ... c₄¦c₃¦c₂¦c₁, this process must end, giving c = p₁·...·p_n·c_n+1 for some primes p₁,…p_n and c_n+1ÎU.

Cor: cÎP Ú cÎC Þ c has a regular prime factorization.

Activity: Prove the above Cor by inducting on the number of primes in a prime factorization of c.

EXERCISES AND PROBLEMS

Pr1 Let R = Z[p].Show U = {1,^-1}. Show that an integer p is prime in Z iff p is prime in R. Show that p+1ÎP but p+2ÎC. Factor p+2 into primes. Show that p has an infinite number of prime factors, and hence cannot be represented as a product of primes. Show that gÎR Û $n gÎZ[p/n!]. Show Z[p/n!] is isomorphic to Z[x], and hence is a UFR. Show n < m Û Z[p/n!] Ì Z[p/m!]. Show that pÎP & p½fg in R Þ p½f Ú p½g in R. Hint, assume p½fg and so $h (hÎR & ph = fg). Then chose n so p,h,f,gÎZ[p/n!].