Unlimited web hosting - 438 ARITHMETIC 4.6.2 16. [M.W] (a) Given that
438 ARITHMETIC 4.6.2 16. [M.W] (a) Given that f(x) is an irreducible polynomial modulo a prime p, of degree n, prove that the pn polynomials of degree less than n form a field under arithmetic modulo f(x) and p. (Note: The existence of irreducible polynomials of each degree is proved in exercise 4; therefore fields with p elements exist for all primes p and all n 2: 1.) (b) Show that any field with p elements has a primitive root element < such that the elements of the field are (0, 1, [, t2,. . . , Epne2}. [Hint: Exercise 3.2.1.2-16 provides a proof in the special case n = 1.1 (c) If f( z ) is an irreducible polynomial modulo p, of degree n, prove that xpm -x is divisible by f(x) if and only if m is a multiple of n. (It follows that we can test irreducibility rather quickly: A given nth degree polynomial f(x) is irreducible modulo p if and only if xpn -x is divisible by f(x) and gcd(xP -2, f(z)) = 1 for all primes o dividing n.) 17. [MB] Let F be a field with 132 elements. How many elements of F have order f, for each integer f with 1 5 f < 132? (The order of an element a is the least positive integer m such that urn = 1.) F 18. [M%] Let U(X) = ~~5~ + . . . + ~0, ZL~ # 0, be a primitive polynomial with integer coefficients, and let V(Z) be the manic polynomial defined by V(X) = IL, - . u(x/u,) = xn + I&-1x-l + un-2unxn-2 +. . .uou, - . (a) Given that w(x) has the complete factorization PI(X). pr(x) over the integers, where each pj(x) is manic, what is the complete factorization of U(X) over the integers? (b) If W(X) = xm + W,-#—l + . . . + Wc iS a faCtOr Of 21(X), prove that wk iS a IUUkipk ofu,”-lpk for0 <- k