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 Monday, November 12. ############################################### # # # Test, Wednesday, November 28 # # # ############################################### The main part of this lesson is on pages 368-381 starting with "Euclidean Domains." Main idea: There is a standard procedure to show unique factorization. Key words: Prime, Unit, Unique Factorization. Goal: Prove unique factorization in the integers and understand what you are doing and why. Previous Assignment 1. Find all the associates of 19 - 17 i in the Gaussian integers. 1 19-17 i = 19-17 i i 19-17 i = 17+19 i -1 19-17 i = -19+17 i -i 19-17 i = -17-19 i 2. Show that the Gaussian Integers have a Euclidean norm. Given a+b i and c+d i, we want to find a p+q i such that a+b i = (c+d i)(p+q i) + r+s i and r^2 + s^2 < c^2 + d^2. a+b i (a+b i)(c-d i) (ac+bd)+(bc-ad)i ----- = -------------- = ------------------ c+d i (c+d i)(c-d i) c^2 + d^2 (ac+bd) bc-ad ------- - p + (--------- -q)i + p+q i c^2+d^2 c^2+d^2) ac+bd bc-ad Letting --------- -p = r and --------- -q = s c^2+d^2 c^2+d^2 We have chosen p and q such that |r| <= 1/2 and |s| <= 1/2. Since n(a+bi) = a^2 + b^2, n(r+s i) <= 2/4. We multiply by the denominator c+d i giving. a+b i = (c+d i)(p+q i) + (c+d i)(r+s i) and n[(c+d i)(r+s i)] = n(c+d i) n(r+s i) <= 2/4 n(r+s i). 3. In the Gaussian integers find Q and R such that 42 + 87 i = (13 + 15 i) Q + R and n(R) < n(13+15 i). 42+87 I 1851 501 I -------- = ---- + ----- 13+15 I 394 394 42+87 I 119 107 ------- = 5+I - ----- + ----- I 13+15 I 394 394 42+87 I = (13+15 I)(5+I) -8-I A = B Q +R n(B) = n(13+15 I) = 394 n(R) = n(-8-I) = 65 Definition: The greatest common divisor of a and b is a number c such that: (1) c divides both a and b (2) if d also divides a and b, then d divides c. Definition: A norm is called Euclidean if given a and b with b =/= 0, there exist a q and r such that a = bq + r and either r = 0 or n(r) < n(b). (* If you refer to the book, there is a second condition *) (* I do not want to get into that condition now. *) Theorem: If there is a Euclidean norm, then the ring has greatest common divisors. Furthermore GCD(A,B) = AX+BY for some X and Y. Proof: Among all the numbers of the form AX+BY, pick one with smallest positive norm. Any element AXo+BYo with smallest positive norm will be a GCD(A,B). (1) We have to show that AXo+BYo divides both A and B. (2) We also have to show that if D divides A and B, then D divides AXo+BYo Obviously, we should use the Euclidean nature of the norm. A = Q(AXo+BYo) + R where n(R) < n(AXo+BYo). We can reorganize this to A(1-QXo)+B(-Yo) = R. Since n(AXo+BYo) was the number with smallest positive n value, we must have R = 0. So AXo+BYo divides A. Similarly, AXo+BYo divides B. The other part is easy. If D divides A and D divides B, then D divides anything of the form AX+BY. In particular, D divides AXo+BYo (* If we try this same technique to the Even Integers, why does it fail? *) Definition: A number p (nonzero and nonunit) is called "irreducible" if whenever p = ab, then either a or b is a unit. (* See Page 356 Definition 7.1.4 *) Definition: A number p (nonzero and nonunit) is called "prime" if whenever p divides a product ab then p divides a or p divides b. (* See Page 360 Definition 7.1.14 *) Theorem: If for all A, B, we can express the GCD(A,B) as AX+BY, then every irreducible is a prime. Proof: Suppose that P divides AB where P is an irreducible. Look at GCD(P,A). Since GCD(P,A) divides the irreducible P, There are two possibilities. Either GCD(P,A) is a unit or GCD(P,A) is an associate of A. If GCD(P,A) is a unit, then PX+AY = U so PX' + AY' = 1 by multiplying by U^(-1). BPX' + ABY' = B. by multiplying by B. Since P divides BPX' and (AB)Y', we get that P divides B. If GCD(P,A) and P are associates, then P divides GCD(P,A) and GCD(P,A) divides A. so P divides A. Theorem: If every irreducible is a prime, then factorization into irreducibles is unique. Proof: Suppose p1 p2 ... pn = q1 q2 ... qm where the pi's and qj's are primes. Since p1 divides the left hand side, p1 must be an associate of some qi. Cancel p1 from both sides. p2 ... pn = q1 q2 ...ui ... qm. Continue the canceling using p2, p3 ... pn. Eventually we get 1 = remaining q's along with some units. There can be no q's remaining because no irreducible is a unit. Thus m = n and each pi can be paired with an associate qj. This says that factoring into irreducibles is unique up to the order of the factors. OUTLINE OF THE EUCLIDEAN UNIQUE FACTORIZATION PROOF. 1. Show factorization into irreducibles. 2. Show Greatest Common Divisors Exist. 3. Show that the Greatest Common Divisor of A and B is expressible as GCD(A,B) = XA+YB 4. Show that any Irreducible is a Prime. 5. Show that elements can be expressed as a product of primes uniquely. Assignment: Using the general proof given above as a model, tailor the proof to work on the integers. 1. Prove that any integer different from {-1,0,1} can be factored into irreducibles. 2. Prove that in the integers, GCD(a,b) exists and furthermore GCD(a,b) = xa+yb for some integers x, y. 3. Prove that in the integers, every irreducible is prime. 4. Prove that in the integers, factorization into irreducibles is unique.