301 Abstract Algebra 2:00 - 2:50 MWF Hentzel 432 Carver hentzel@iastate.edu Web Page http://www.math.iastate.edu/hentzel/class.301 Text: A First Course in Abstract Algebra, sixth Edition by John B. Fraleigh Course: Chapter 1,2,3,4,5 Wednesday, November 14. ############################################### # # # Test, Wednesday, November 28 # # # ############################################### The main part of this lesson is on pages 368-381 starting with "Euclidean Domains." Main idea: Prepare for the test, not the first meeting after Thanksgiving, but the second meeting. Key words: domain, UFD, PID, Euclidean Domain, Euclidean algorithm, Goal: Get an A on the next test. Assignment: Page 380-381 work all problems except Problem 15. If you do not know a terminology like PID which means "Principle ideal domain", omit that problem. You should know what a domain is. The meaning of domain is essentially what we have been studying. That is, Subsets of the complex numbers which are closed under addition, subtraction, and multiplication. Examples are the integers, the Gaussian Integers, Z[Sqrt[-6]]. Another example is polynomials. The criterion for a domain are addition, subtraction, commutative multiplication, and ab = 0 implies a = 0 or b = 0. 1. n[5] = 25. The nontrivial factors involve {1,2}. (2+ I)(2- I) = 5. Both factors are irreducible because their norm is 5 which is a prime. 2. n[7] = 49 7 is not the sum of two squares therefore 7+0 I cannot be factored nontrivially. 3. n[4+3 i] = 25 A nontrivial factor must have norm 5. The factors involve {1,2}. 4+3 I = (-2+ I)(-1- 2 I) Both factors are irreducible because their norm is a prime. 4. n[6-7 i ] = 85 = 5x17 The possible factors are 1 and 2 and 4 and 1 (4+I)(1-2I) = 6-7 I. Since the norms of both factors is a prime integer, both factors are irreducible. 5. 6 does not factor uniquely (up to associates) into irreducibles in Z[Sqrt[-5]]. 6 = 2x3 = (1+Sqrt[-5])(1-Sqrt[-5]) 2 is irreducible n(a+bSqrt[-5]) = a^2 + 5 b^2 and is at least 5 unless b = 0. Since 2 and 3 are irreducible in the integers, they are then irreducible in Z[Sqrt[-5]]. The only way (1+Sqrt[-5]) or (1-Sqrt[-5]) can factor non trivially is if the factors have norm 2 or 3. There are no numbers with norm 2 or 3. 6. Consider a = 7+2 I and b = 3-4 I in Z[I]. Find q and r in Z[i] such that a = bq+r with N[r] < n[b]. 7+2 I ------ = 13/25 + 34/25 I = 1 + I + (-12/25 +9/25 I) 3-4 I 7+2 I = (3-4I)(1+I)+(3-4I)(-12/25+9/25 I) 7+2 I = (3-4I)(1+I)+ 3I N[3-4I] = 25. N[3I] = 9 7. Use a Euclidean algorithm in Z[i] to find a gcd of 8+6I and 5-15 I in Z[i] N[8+6I] = 100 N[5-15I] = 250 -1-I --------- 8+6I | 5-15 I -2-14 I 1+ I --------- ---------- 7 - I | 8+6 I 8+6 I ------- 0 GCD(8+6 I,5-15 I) = 7-I -1-I 1+I 1 -1-I 1-2 I 0 1 1+ I (-1- I)(1+ I)-1(1-2I) = -1 (+1+ I)(1+ I)+1(1-2I) = +1 (+1+ I)(1+I)(7-I)+1(1-2I)(7-I) = 7-I (1+I)(8 + 6 I)+1(5 - 15 I) = 7-I 8. a. True Z[i] is a PID. Z[i] has the division algorithm with the Euclidean property. Therefore it is a Unique Factorization Domain which then is a Principle Ideal Domain. b. True Z[i] is a Euclidean Domain domain because given a and b, there exists q and r such that a = bq+r and r = 0 or n(r) < d(b). c. True Every integer in Z is a Gaussian integer. x = x + 0 i. d. False Every complex number is a Gaussian integer. Things like e + Pi i are complex numbers. The Gaussian integers are those where the numbers are integers. e. True A Euclidean algorithm holds in Z[i]. Given a+bi and c+di, round the coefficients of (a+bi)/(c+di) to p+qi. Letting r+si = (a+bi)-(c+di)(p+qi) gives the answer and n(r+si) <= 1/2 n(c+di). f. True A multiplicative norm on an integral domain D is sometimes an aid in finding irreducibles of the domain. It is used to create the factors to check and also to prove that factors are irreducibles. g. True If N is a multiplicative norm on an integral domain D, then N(u) = 1 for every unit u of D. N(1)^n = N(1) so N(1) = 1. Since N(u) divides 1, we must have N(u) = 1 for every unit u. h. False If F is a field, then the function defined by N(f(x)) = (degree of f(x)) is a multiplicative norm on F[x]. N(f(x) g(x) ) = N(f(x)) + N(g(x)) and to be a multiplicative norm one needs instead that N(f(x) g(x)) = N(f(x)) N(g(x)). i. True If F is a field, then the function defined by N(f(x)) = 2^(degree of f(x)) for f(x) =/= 0 and N(0) = 0 is a multiplicative norm on F[x] according to our definition. j. True Z[Sqrt[-5]] is an integral domain but not a UFD. Subrings of the complex numbers are always integral domains. Since 6 = 2x3 = (1+Sqrt[-5])(1-Sqrt[-5]) is a factorization into irreducibles in two ways, Z[Sqrt[-5]] is not a unique factorization domain. 9. Let D be an integral domain with a multiplicative norm N such that N(a) = 1 for a in D if and only if a is a unit of D. Let Pi be such that N(pi) is minimal among all N(b) > 1 for b in D. Show that Pi is irreducible in D. Proof. If pi = cd, then N(pi) = N(c) N(d). If neither c not d is a unit, then N(c) < N(pi) and N(d) < N(pi). Then since c is not a unit, 1 < N(c) < N(pi). This is a contradiction. Thus either c or d is a unit and the other is of course, an associate. 10. a. Show that 2 is equal to the product of a unit and the square of an irreducible in Z[i]. (-I) (1+I)^2 = 2, b. Show that an odd prime p in Z is irreducible in Z[i] if and only if p == 3 (mod 4). Hint: Let p be an odd prime in Z. Then p = a^2 + b^2 for integers a and b in Z if and only if p ==1 mod 4. Proof: =====> Suppose that p is an odd prime which is irreducible. There are 4 possibilities. p==0,p==1,p==2,p==3 mod 4. If p==0 mod 4, then 4 divides an odd prime which is impossible. If p==2 mod 4, then 2 divides an odd prime which is impossible. If p==1 mod 4 then p factors non trivially by the theorem. If p==3 mod 4, then p cannot factor because if it did, then p = (a+ib)(a-ib) and the theorem says that only happens when p==1 mod 4. <========== Suppose that p == 3 (mod 4). Then p =/= a^2 + b^2 by the theorem. If p factors nontrivially as p = (a+bi)(c+di) then N(p) = p^2 = (a^2+b^2)(c^2+d^2). But then a^2+b^2 = p and c^2+d^2 = p. This is a contradiction. Thus p must be irreducible. 11. Prove Lemma 7.3.2. In Z[i], the following properties of the norm function N hold for all a, b in Z[i]. 1. N(a) >= 0. Since N(a+bi) = a^2 + b^2, N(a+bi) >= 0. 2. N(a) = 0 if and only if a = 0. If 0 = N(a+bi) = a^2 + b^2, then a = 0 and b = 0. Thus a+bi = 0. 3. N(ab) = N(a)N(b). ------ We will use the fact that (a+bi) = (a-bi) is multiplicative. ------------ -------------- (a+bi)(c+di) = ac-bd+(ad+bd)i = (ac-bd)-(ad+bc)i = (a-bi)(c-di) ------ Now N(a+bi) = (a+bi)(a+bi) = a^2 + b^2. ------------ N((a+bi)(c+di)) = (a+bi)(c+di) (a+bi)(c+di) ------ ------ = (a+bi)(c+di) (a+bi) (c+di) ------ ------ = (a+bi)(a+bi) (c+di)(c+di) = N(a+bi) N(c+di) 12. Prove that N of Example 7.3.9 is multiplicative. That is N(ab) = N(a)N(b) for a b in Z[Sqrt[-5]]. N(a+bSqrt[-5]) = a^2 + 5 b^2. ------------- First the map (a+bSqrt[-5]) = a-bSqrt[-5] is multiplicative. -------------------------- ------------------------ (a+bSqrt[-5])(c+dSqrt[-5]) = (ac-5bd)+(ad+bc)Sqrt[-5] = (ac-5bd)-(ad+bc)Sqrt[-5] = (a-bSqrt[-5])(c-dSqrt[-5]). ------------- Now N(a+bSqrt[-5]) = (a+bSqrt[-5])(a+bSqrt[-5]) = a^2 + 5 b^2. Now N((a+bSqrt[-5])(c+dSqrt[-5])) -------------------------- = (a+bSqrt[-5])(c+dSqrt[-5]) (a+bSqrt[-5])(c+dSqrt[-5]) ------------- ------------- = (a+bSqrt[-5])(c+dSqrt[-5]) (a+bSqrt[-5]) (c+dSqrt[-5]) ------------- ------------- = (a+bSqrt[-5]) (a+bSqrt[-5]) (c+dSqrt[-5]) (c+dSqrt[-5]) = N(a+bSqrt[-5]) N(c+dSqrt[-5]) 13. Let D be an integral domain with a multiplicative norm such that N(a) = 1 for a in D if and only if a is a unit of D. Show that every nonzero nonunit of D has a factorization into irreducibles in D. Proof: Starting with a nonzero nonunit a, factor a and continue factoring the factors. Since if b = cd nontrivially, then N(b) = N(c)N(d) and neither c nor d is a unit. Thus N(c) and N(d) are both greater than 1. Thus N(b) > N(c) and N(b) > N(d). So with each successive factorization, the Norm of the factors drops. Since the norm of the factor is greater than 1, there can only be N(b) successive factorings. Therefore the process must stop with irreducibles. Thus b is the product of a finite number of irreducibles. 14. Use a Euclidean algorithm in Z[i] to find a gcd of 16+7i and 10-5i in Z[i] N(16+7i) = 305 N(10-5i) = 125 1+ I --------- 10-5 I | 16+7 I 15+5 I -5 I ------- ----------- 1+2 I | 10-5 I 10-5 I ------- 0 GCD(16+7 I,10-5 I) = 1+2I 16+7 I = (1+2 I)(6 - 5 I) 10-5 I = (1+2 I)(-5 I) 1+I -5I 1 1+I 6 - 5 I 0 1 -5 I (1+I)(-5I)-1(6-5I) = -1 (-1-I)(-5I)+1(6-5I) = 1 (-1-I)(-5I)(1+2I)+1(6-5I)(1+2I) = 1+2I (-1-I)(10-5I)+1(16+7I) = 1+2 I 15. OMIT 16. Let n in Z+ be square free, that is, not divisible by the square of any prime integer. Let Z[Sqrt[-n]] = {a + b Sqrt[-n]}. (a) Show that the norm N, defined by N(a) = a^2 + n b^2 for a = a+bSqrt[-n] is a multiplicative norm on Z[Sqrt[-n]] Certainly N(a) >= 0 and N(a) = 0 if and only if a = 0. ------------- The map (a+bSqrt[-n]) = a-bSqrt[-n] is multiplicative. Proof. -------------------------- ------------------------ (a+bSqrt[-n])(c+dSqrt[-n]) = (ad-5bc)+(ad+bc)Sqrt[-n] = (ad-5bc)-(ad+bc)Sqrt[-n] = (a-bSqrt[-n])(c-dSqrt[-n]) ------------- ------------- = (a+bSqrt[-n]) (c+dSqrt[-n]) ------------- N(a+bSqrt[-n]) = (a+bSqrt[-n])(a+bSqrt[-n]) = (a+bSqrt[-n])(a-bSqrt[-n]) = a^2 + n b^2 = N(a+bSqrt[-n]). N((a+bSqrt[-n])(c+dSqrt[-n])) ------------------------- = (a+bSqrt[-n])(c+dSqrt[-n]) (a+bSqrt[-n])(c+dSqrt[-n]) ------------- ------------ = (a+bSqrt[-n])(c+dSqrt[-n]) (a+bSqrt[-n]) (c+dSqrt[-n]) ------------- ------------- = (a+bSqrt[-n]) (a+bSqrt[-n]) (c+dSqrt[-n]) (c+dSqrt[-n]) = N(a+bSqrt[-n]) N(c+dSqrt[-n]) (b) Show that N(a) = 1 for a in Z[Sqrt[-n]] if and only if a is a unit of Z[Sqrt[-n]]. If N(a+bSqrt[-n]) = a^2 + n b^2. This equals 1 if and only if b = 0 and a^2 = 1. It only happens for 1,-1. So if N(a+bSqrt[-n]) = 1, then a+bSqrt[-n] is a unit. Suppose that a+bSqrt[-n] is a unit. Then there exist c+dSqrt[-n] such that (a+bSqrt[-n])(c+dSqrt[-n]) = 1. That means that N(a+bSqrt[-n]) N(c+dSqrt[-n]) = N(1). So (a^2 + nb^2)(c^2 + nd^2) = 1. This can only happen if both factors are 1. Thus (a+bSqrt[-n]) = 1 or -1. (c) Show that every nonzero a in Z[Sqrt[-n] that is not a unit has a factorization into irreducibles in Z[Sqrt[-n]]. Proof by induction. Suppose there were elements which are nonzero, nonunits which are not expressible as a product of irreducibles. Of all the nonzero, nonunits which are not expressible as a product of irreducibles, let a have the smallest norm If a were irreducible, then a is a product of irreducibles which is a contradiction. Therefore a = bc where neither b nor c is a unit nor zero. Now N(a) = N(b) N(c) and since N(b) > 1 and N(c) > 1, we must have N(a) > N(b) and N(a) > N(c). By induction, b and c must be expressible as a product of irreducibles. Thus a itself must be expressible as a product of irreducibles. This contradiction means that the set of elements which are nonzero, nonunits, not expressible as a product of irreducibles is empty. 17. Repeat Exercise 16 for Z[Sqrt[n] = {a+bSqrt[n] | a,b in Z} with N defined by N(a+bSqrt[n]) = | a^2 - n b^2|. (a) Show that the norm N, defined by N(a) = |a^2 - n b^2| for a = a+bSqrt[n] is a multiplicative norm on Z[Sqrt[n]] Certainly N(a) >= 0 and N(a) = 0 if and only if a^2 = n b^2. Here it is necessary to know that n is not a perfect square. Since n was Square free, we know that a^2 = n b^2 implies a = b = 0. ------------- The map (a+bSqrt[n]) = a-bSqrt[n] is multiplicative. Proof. ------------------------ ----------------------- (a+bSqrt[n])(c+dSqrt[n]) = (ad-5bc)+(ad+bc)Sqrt[n] = (ad-5bc)-(ad+bc)Sqrt[n] = (a-bSqrt[n])(c-dSqrt[n]) ------------ ------------ = (a+bSqrt[n]) (c+dSqrt[n]) ----------- N(a+bSqrt[n]) = |(a+bSqrt[n])(a+bSqrt[n])| = |(a+bSqrt[n])(a-bSqrt[n])| = |a^2 - n b^2| = N(a+bSqrt[n]). N((a+bSqrt[n])(c+dSqrt[n])) ------------------------ = |(a+bSqrt[n])(c+dSqrt[n]) (a+bSqrt[n])(c+dSqrt[n])| ------------ ------------ = |(a+bSqrt[n])(c+dSqrt[n]) (a+bSqrt[n]) (c+dSqrt[n])| ------------ ------------ = |(a+bSqrt[n]) (a+bSqrt[n]) (c+dSqrt[n]) (c+dSqrt[n])| ------------ ------------ = |(a+bSqrt[n]) (a+bSqrt[n])||(c+dSqrt[n]) (c+dSqrt[n])| = N(a+bSqrt[n]) N(c+dSqrt[n]) (b) Show that N(a) = 1 for a in Z[Sqrt[n]] if and only if a is a unit of Z[Sqrt[n]]. If N(a+bSqrt[n]) = 1, then | (a+bSqrt[n])(a-bSqrt[n])| = 1 Then the inverse of a+bSqrt[n] is a-b(Sqrt[n] or -a+bSqrt[n]. If a+bSqrt[n] is a unit, Then 1 = (a+bSqrt[n])(c+dSqrt[n]) and so 1 = N(a+bSqrt[n]) N(c+dSqrt[n]). Since N(a+bSqrt[n]) divides 1, N(a+bSqrt[n]) = 1. (c) Show that every nonzero a in Z[Sqrt[n] that is not a unit has a factorization into irreducibles in Z[Sqrt[n]]. Proof by induction. Suppose there were elements which are nonzero, nonunits which are not expressible as a product of irreducibles. Of all the nonzero, nonunits which are not expressible as a product of irreducibles, let a have the smallest norm If a were irreducible, then a is a product of irreducibles which is a contradiction. Therefore a = bc where neither b nor c is a unit nor zero. Now N(a) = N(b) N(c) and since N(b) > 1 and N(c) > 1, we must have N(a) > N(b) and N(a) > N(c). By induction, b and c must be expressible as a product of irreducibles. Thus a itself must be expressible as a product of irreducibles. This contradiction means that the set of elements which are nonzero, nonunits, not expressible as a product of irreducibles is empty. 18. Show by a construction analogous to that given in the proof of Theorem 7.3.4 that the division algorithm holds in the integral domains Z[Sqrt[-2]], Z[Sqrt[2]], Z[Sqrt[3]] for v[a] = N[a] for nonzero a in one of these domains (see Exercise 16 and 17). (Thus these domains are Euclidean. See Hardy and Wright [29] for a discussion of which domains Z[Sqrt[n]] and Z[Sqrt[-n]] are Euclidean.) Given a+bx (ac+xbd)+(ad+bc)x ----- = ----------------- c+dx c^2 - d^2 x^2 ac+xbd ad+bc = ----------- - p +(----------- - q )x + p+qx c^2-d^2 x^2 c^2-d^2 x^2 = r+sx + p+qx where |r| <= 1/2 and |s| <= 1/2. Now a+bx = (c+dx)(r+sx) + (p+qx)(c+dx) And so (c+dx)(r+sx) must be integral and N((c+dx)(r+sx)) = N(c+dx) N(r+sx) <= (1/4 + x^2/4) N(c+dx) This works if x^2 = 2 or -2. It does not work if x^2 = -3. However it does work for x^2 = 3 which was what was needed.