MATHEMATICS 152, FALL 2004METHODS OF DISCRETE MATHEMATICSHomework Problems relevant to the second quizLast modified: October 15, 2004Reading• Biggs, Chapter 22.• Biggs, Chapter 23, especially 23.1–23.4.• The handout on Affine Geometry.Required ProblemsDue dates are subject to minor adjustments, since they are based on guessesabout how far we will get in class.The second quiz will be on Thursday, November 18, not on November 9 asshown on the schedule in the syllabus.Problems due Tuesday, Oct. 261. Show that H = {I, (12)} is not a normal subgroup of S4by computingits conjugate subgroups.2. Show that J = {I, (123), (132)} is a normal subgroup of S3by computingits conjugate subgroups. What is the quotient group S3/J?3. Consider the group G = (Z×13, ⊗) and the subgroup H generated by [4].Determine the quotient group G/H by writing down its elements (thecosets) and writing a group table for them.4. Consider the ring R = M2(Z2), that is, the 2 × 2 matrices with entriesfrom the field Z2.(a) How many elements does R have?(b) Find all elements that have multiplicative inverses, and list themwith their inverses.5. Consider the ring of Gaussian integers, R = Z[i] = {a + bi|a, b ∈ Z},where i2= −1. With the usual addition and multiplication from thecomplex numbers, it may be shown that R is a ring. Which elementshave multiplicative inverses, and what are they?16. Problem #22.1.3 in Biggs: Show that if x and y are members of a ringR then (−x)(y) = −(xy) and (−x)(−y) = xy. At each stage of theproof, explain which property of R you are using. You should not needto assume that multiplication is commutative or that a multiplicativeidentity 1 exists, though with Biggs’s definition of ring you are allowedto assume the existence of a multiplicative identity.7. Consider the quotient ring R = Z3[x]/hq(x)i where q(x) = x3+ x + 1.(This polynomial is reducible over Z3, so R is not a field!)How many elements are in R? Compute the products [2x + 1][x2] and[x + 2][x2+ 2x + 2] in R.Problems due Tuesday, Nov. 28. Exhibit an isomorphism between the non-zero elements of F8(that is,the multiplicative group of the field) and the elements of Z7(consideredas an additive group).9. Use Euclid’s gcd algorithm to find the greatest common divisor of x3+4x2+ 2x + 2 and 2x3+ 4x2+ 3 as polynomials in Z5[x]. (The gcd is aquadratic polynomial.)10. The polynomial q = x2+ 3x + 3 is irreducible over Z5and so can be usedto construct the field F25. Use Euclid’s algorithm to find the inverse ofp = [x + 2] in F25by finding polynomials m and n such that mp + nq =1.11. Consider the quotient ring R = Z5[x]/hq(x)i where q(x) = x2+ 2. q(x)is irreducible, so this is a field.(a) How many elements are in R?(b) Find a formula for the multiplicative inverse of the element [b+ax],where a 6= 0. (Hint: “Rationalize the denominator.” x =√−2. Tosimplify1[b+ax], multiply numerator and denominator by [b − ax].(c) Find the orders of the elements [x] and [x + 1].12. Biggs, problem 3 on page 317.13. In the large affine faculty senate two “triangles” are Danny-Gavin-Viola(ABC) and Helen-Sally-Xenia (A0B0C0). Show that these six instructorssatisfy the conditions and the conclusion of the Desargues axiom.14. In the medium affine faculty senate, choose the library committee, withJane as the additive identity. Add Greg and Mike, first using Kate as theauxiliary point, then using Irma. Draw a single diagram representing theaddition with both auxiliary instructors, attaching a committee nameto each line and an instructor name to each point. Identify the two2“triangles” that are related by Desargues’ theorem in the proof that theanswer is independent of the choice of instructor.15. Use the data for the medium affine faculty senate. Choose the librarycommittee, with Jane as the additive identity and Dave as the multi-plicative identity. Multiply Greg by Mike, then multiply Mike by Greg,in each case using Kate as the auxiliary point. Draw a single diagramrepresenting the multiplication in both orders, attaching a committeename to each line and an instructor name to each point. Identify thedegenerate hexagon of six instructors to which Pappus’ Theorem (axiomA5) must be applied to show that the multiplication is commutative.16. Suppose that A and E are members of a committee of an affine facultysenate whose additive identity is O. Describe a method for constructingthe instructor C such that A + C = E using auxiliary instructor B.Prove directly from the axioms that us ing a different instructor B0onthe same committee as O and B leads to the same C. (Of course, this istrue for arbitrary B0, but the proof becomes tedious). Include a diagramto illustrate how your construction would look in the Euclidean plane,for which your proof is also valid.17. Choose the quality committee in the large affine faculty senate, withBetty as the additive identity O, Isaac as A, Kevin as C, Yoric as E.Choose James as auxiliary instructor B. Carry out the addition (A +C) + E and A + (C + E), using auxiliary instructors B0and D exactlyas described in the notes and in the diagrams on the Web.(a) Who is B0, and who is D?(b) Who is the sum A + C + E?(c) Redraw the diagram from the Web that shows that addition is asso-ciative, with names attached to all the instructors and committees.If two distinct points in the diagram have the same name, don’tworry – the diagram is for Euclidean geometry and you are doingfinite geometry.Problems due Tuesday, Nov. 918. Suppose that C and E are members of a committee of an affine facultysenate whose additive identity is O and whose multiplicative identity is I.Describe a method for constructing the instructor A such that AC = Eusing auxiliary member B. Prove directly from the axioms that usinga different member B0on the same committee as I and B leads to thesame A. (Of course, this is true for arbitrary B0, but the proof becomestedious). Include a diagram to illustrate how your construction wouldlook in the Euclidean plane, for which your proof is also valid.319. Consider the yearbook committee in the large affine faculty senate. ChooseHelen as the additive identity 0 and Sally as the multiplicative identity I.Generate the addition and multiplication tables using affine.exe(downloadable,but for Windows only) or Luke Gustafson’s software (from the Web site),and use them to identify the members of the committee with the elements0, 1, 2, 3, 4 of Z5.20. Consider the large affine faculty senate. Choose