Test 3 Wednesday, November 28, 2001 Math 301 Abstract Algebra Hentzel The Euclidean property for the integers is: Given a and b, b =/= 0, then there is a q and r such that a = bq+r and 0 <= r < |b|. In this test you may assume that the integers have the Euclidean property. 1. Prove that in the integers we have factorization into irreducibles. ----------------------------------------------------------- Proof: Since |ab| = |a||b|, if neither |a| nor |b| is 1, then 0 < |a| < |ab| and 0 < |b| < |ab|. Let x be an integer different from -1,0,1. Then x can be expressed as a product of irreducibles. The proof is by induction on |x|. Suppose that there is some x different from -1,0,1 which is not a product of irreducibles. Let x be such an element with |x| minimal. If x is irreducible, then we consider x to be a product of irreducibles. If x = yz, and neither y nor z is -1,0,1, then |y|<|x| and |z| < |x|. Since x was the element with smallest absolute value which was not a product of irreducibles, this means that y is a product of irreducibles and z is a product of irreducibles. Thus x is also a product of irreducibles. This is a contradiction. It must be true that the set of elements not -1,0,1 which can not be expressed as a product of irreducibles is empty. Thus every element different form -1,0,1 is a product of irreducibles. -------------------------------------------------------- 2. Euclidean property implies Greatest common divisor property. (a) What is the greatest common divisor property? ----------------------------------------------------------- Given two elements a,b not both zero, there exists an element c such that (a) c divides a and c divides b and (b) If d divides a and d divides b then d divides c. ------------------------------------------------------------- (b) Prove that the integers have the greatest common divisor property. ------------------------------------------------------------- ans: Given a and b not both zero, let S = {xa+yb | x,y in Z}. Since a and b are not both zero, S contains positive elements. Let c = a xo+b yo be the smallest positive number in S. We claim that c is the greatest common divisor of a and b. (a) We will show that c divides a. The proof that c divides b is similar. Using the Euclidean property, a = cq + r and 0 <= r < |c|. So a = (a xo+b yo)q + r and a(1-xoq) +b(-yoq) = r. Since r is a linear combination of a and b, r is in S. Since 0 <= r < |c|, and c = |c| was the smallest positive number in S, we conclude that r = 0. Thus c | a. (b) We will show that if d divides a and d divides b, then d divides c. This is immediate since c = a xo + b yo and anything that divides a and b will divide the linear combination a xo + b yo. ------------------------------------------------------------------- 3. Every irreducible is a prime. (a) What is the definition of irreducible and prime? ----------------------------------------------------------------- A nonzero, nonunit number a is irreducible if whenever a = xy, then either x or y is a unit. A nonzero, nonunit number a is a prime if whenever a divides xy, then a divides x or a divides y. -------------------------------------------------------------------- (b) Prove in the integers that every irreducible is a prime. ------------------------------------------------------------- Suppose that p is irreducible and that p divides ab. Look at GCD(p,a). Since GCD(p,a) divides the irreducible p, then GCD(p,a) = u a unit, or GCD(p,a) = u p where u is a unit. If GCD(p,a) = u, then p xo + a yo = 1 and by multiplying by b we get pbxo + ab yo = b. Since p divides pbxo and p divides (ab)yo we get p divides b. If GCD(p,a) = up then p divides GCD(p,a) and GCD(p,a) divides a so p divides a. ---------------------------------------------------------------- 4. Prove that the integers have unique factorization into irreducibles. --------------------------------------------------------- Suppose that p1 p2 ... pm = q1 a2 ... an where p's and q's are irreducible. Since p1 is a prime which divides the left hand side, p1 divides some qi on the right hand side. So qi = p1 ui. Cancel off p1 and continue until all the p's are cancelled. Then we have 1 = Product of remaining q's and the units. There cannot be any q's left since such a q would divide 1 and be a unit. Thus the number of p's equals the number of q's and each irreducible factor pj is paired with an irreducible factor qi. Thus the factorization into primes is unique up to associates. --------------------------------------------------------------- 5. Prove that the function n(x+y Sqrt[-3]) = x^2 + 3 y^2 is multiplicative on Z[Sqrt[-3]]. -------------------------------------------------------------- ------------ Define a conjugate operation a+b Sqrt[-3] = a-b Sqrt[-3] Conjugation is multiplicative since ---------------------------- -------------------------- (a+b Sqrt[-3])(c+d Sqrt[-3]) = (ac-3bd)+(ad+bc) Sqrt[-3]) = (ac-3bd)-(ad+bc) Sqrt[-3] = (a-b Sqrt[-3])(c-d Sqrt[-3]) ------------- ------------- = (a+b Sqrt[-3])(c+d Sqrt[-3]) -------------- n(x+y Sqrt[-3]) = x^2 + 3 y^2 = (x+y Sqrt[-3]) (x+y Sqrt[-3]) ---- _ _ _ _ Now n(XY) = (XY)(XY) = X Y X Y = (X X)(Y Y) = n(X) N(Y) ------------------------------------------------------------- 6. In the Gaussian Integers, (a) Find the Greatest Common Divisor of -129 + 953 i and 32 + 6 I. ------------------------------------------------------------------- 1 + 29 I --------------- 32+6 I | -129 + 953 I -142 + 934 I 1-I ----------- ------------------ 13 + 19 I | 32 + 6 I 32 + 6 I -------- 0 The Greatest Common Divisor is 13 + 19 I. -------------------------------------------------------------------- (b) Find Gaussian Integers x and y such that x(-129 + 953 i) + y(32 + 6 i) = GCD(-129 + 953 i, 32 + 6 i). --------------------------------------------------------------------- 1 + 29 I 1-I 1 1+29I 31+28I 0 1 1-I (1+29I)(1-I) - 1(31+28I) = -1 (1+29I)(1-I)(-13-19I) - 1(31+28I)(-13-19I) = 13+19I (1+29I)(-32 - 6 I) -1(129 - 953 I) = 13+19I (-1-29I)( 32 + 6 I) +1(-129 + 953 I) = 13+19I y x GCD ------------------------------------------------------------------- 7. Find q and r in Z[Sqrt[3]] such that 80+ 3 Sqrt[3] = (12 + 7 Sqrt[3])q + r and n(r) < n(12 + 7 Sqrt[3]). n(a+b Sqrt[3]) = | a^2 - 3 b^2 |. (80+3 Sqrt[3])/(12+ 7 Sqrt[3]) (80+3 Sqrt[3]) - (12+7 Sqrt[3])(-299 + 175 Sqrt[3]) = -7 - 4 Sqrt[3] (-7-4 Sqrt[3]) (-7+4 Sqrt[3]) = 1