MATHEMATICS 152, FALL 2003METHODS OF DISCRETE MATHEMATICSOutline #6 (Rings and Fields, especially Finite Fields)None of this material is needed for the half-hour quiz on Oct. 9, which willcover outlines 1 through 5 and the first three homework assignments.We define rings and fields, provide basic examples, construct more complexexamples, and study the structure of these objects.1. Define a ring as a set with two binary operations, traditionally denoted+ and ·, satisfying a set of axioms that Biggs summarizes as R1, R2,and R3. Expand R1 into A1-A5, R2 into M1-M2, and call R3 D. A ringwhich satisfies M3 is said to be a ring with identity;Axioms M5 and M4are the ”extra algebraic properties that Biggs mentions at the top of p.197. A ring which also satisfies M4 is said to be a division ring; and aring which also satisfies M5 is said to be a commutative ring. A ring thatsatisfies all eleven axioms is said to b e a field.Write out all the axioms explicitly. Then, by considering (1+1)(a+b)and using the distributive law, prove that, for the case of a field, theaxiom that addition is commutative (you probably called it A5) followsfrom the other axioms. (Sections 22.1–22.3.)2. Show that the following examples satisfy the axioms above:(a) the integers, Z, which form a commutative ring with identity,(b) the congruence classes of integers modulo n , denoted Zn, whichform a commutative ring with identity in all cases and a field whenn is prime,(c) the polynomials with real coefficients, denoted R[x], which form acommutative ring with identity.(d) the n × n matrices with real entries, denoted Mn(R), which form aring with identity (and a field in the special case n = 1).(Sections 22.1, 22.3, and 22.4.)3. Consider the more abstract rings of polynomials, F [x], where F is anyfield. (In particular, we are interested in the case where F = Zpfor aprime p.) State the Division Algorithm and the Euclidean Algorithm forpolynomial rings. (Sections 22.4–22.6.)14. Construct the equivalence classes of polynomials modulo q(x), for aspecified polynomial q(x) of degree n. How many such equivalenceclasses are there when F = Zp? Define addition and multiplicationon the set of equivalence classes by [a(x)] + [b(x)] = [a(x) + b(x)] and[a(x)][b(x)] = [a(x)b(x)], and show that with these definitions, the set ofequivalence classes forms another ring, known as a quotient ring. (Sec-tions 23.1 and 23.3.)5. In the construction above, show that the quotient ring is in fact a fieldwhen q(x) is irreducible. Give examples of irreducible polynomials ofdegree 2 and 3 in the polynomial rings F [x] when F = Z2, Z3, and Z5.(Pay special attention to the case p = 3 and q(x) = x2+ 1., done inBiggs section 23.1) (Sections 22.7–22.8 and 23.3.)6. For the case where p = 2 and q(x) = x2+ x + 1, the four elements of thefield are [0],[1], [x], and [x + 1]. Show how to build up the multiplicationtable for this field of four elements, F4, by using the rules that• All coefficients are in Z2so that 1 + 1 = 0.• x2+ x + 1 = 0 so that x2can always be replaced by x + 1.(See Exercise 23.2 in Biggs)7. By counting the number of distinct products of non-zero monic linearpolynomials with coefficients in Zpand the number of non-zero monicquadratic polynomicals with coefficients in Zp, prove that there exists atleast one irreducible monic quadratic polynomial for any prime p (Section22.8).8. For the field F9with irreducible polynomial x2+ 2x + 2 (note – this isnot the same polynomial that Biggs uses in section 23.1) make a tableof all the powers of [x].Show how to use this result to find the inverseof any nonzero e lement and to do multiplication by means of addition.(This is the finite case of logarithms!)(Section