Construction - University of Connecticut

1 FINITE FIELDSKEITH CONRADThis handout discusses finite fields: how to construct them, properties of elements in afinite field, and relations between different finite fields. We writeZ/(p) andFpinterchange-ably for the field of is an executive summary of the main results. Every finite field has prime power order. For every prime power, there is a finite field of that order. For a primepand positive integern, there is an irreducible (x) of degreeninFp[x], andFp[x]/( (x)) is a field of orderpn. All finite fields of the same size are isomorphic (usually not in just one way). If [Fp( ) :Fp] =d, theFp-conjugates of are , p, p2,.., pd 1. Every finite extension ofFpis a Galois extension whose Galois group overFpisgenerated by thepth power a primepand a monic irreducible (x)inFp[x]of degreen, the ringFp[x]/( (x))is a field of cosets mod (x) are represented by remaindersc0+c1x+ +cn 1xn 1, ci Fp,and there arepnof these.

2 Since the modulus (x) is irreducible, the ringFp[x]/( (x)) is afield using the same proof thatZ/(m) is a field whenmis prime. Example fields of order 8 areF2[x]/(x3+x+ 1) andF2[x]/(x3+x2+ 1).Example fields of order 9 areF3[x]/(x2+ 1) andF3[x]/(x2+x+ 2).Example polynomialx3 2 is irreducible inF7[x], soF7[x]/(x3 2) is a field oforder 73= Donottry to create a field of order 8 asZ/(8). That is not a field. Similarly,Z/(9) is not a field. The ringZ/(m) is a field only whenmis a prime number. In order tocreate fields of non-prime size we must do something other than look atZ/(m).We will see that every finite field is isomorphic to a field of the formFp[x]/( (x)), sothese polynomial constructions give us working models of every finite field. However, notevery finite field is literally of the formFp[x]/( (x)). For instance,Z[ 2]/(3) is anotherfield of size 9 (which is isomorphic toF3[x]/(x2 2) =F3[x]/(x2+ 1)).Theorem finite field has prime power each commutative ringRthere is a unique ring homomorphismZ R, wherem7 1 + 1 + + 1 mtimes,ifm 0, (1 + 1 + + 1 |m|times),ifm < apply this to the case whenR=Fis a finite field.

3 The kernel ofZ Fis nonzerosinceZis infinite andFis finite. Write the kernel as (m) =mZfor an integerm >0, soZ/(m) embeds as a subring ofF. A subring of a field is a domain, somhas to be a primenumber, saym=p. Therefore there is an embeddingZ/(p) F. ViewingFas a vectorspace overZ/(p), it is finite-dimensional sinceFis finite. Lettingn= dimZ/(p)(F) andpicking a basis{e1,..,en}forFoverZ/(p), elements ofFcan be written uniquely asc1e1+ +cnen, ci Z/(p).Each coefficient haspchoices, so|F|=pn. Lemma a finite field, the groupF is |F|, so|F |=q 1. Letmbe the maximal order of the elements of thegroupF , som|(q 1) by Lagrange s theorem. We will showm=q is a theorem from group theory (see the appendix) that in a finiteabeliangroup, allorders of elements divide the maximal order of the elements1, so everytinF satisfiestm= 1. Therefore all numbers inF are roots of the polynomialxm 1. The number ofroots of a polynomial over a field is at most the degree of the polynomial, soq 1 the order of some element inF , we havem|(q 1), som q 1.

4 Thereforem=q 1, so some element ofF has orderq 1. Example :=F3[x]/(x2+ 1), there are 8 nonzero elements. The powers ofxarex, x2= 1 = 2, x3= 2x, x4= 2x2= 2 = 1,soxdoes not generateF . Butx+ 1 does: its powers are in the table + 1 2x2x+ 1 2 2x+ 2x x+ 2 1 Example primep, (Z/(p)) is cyclic: (Z/(p)) ={a,a2,..,ap 1modp}forsomea6 0 modp. A constructive proof of this, using the prime factorization ofp 1, is inSection 6 a finite fieldF, the multiplicative groupF is cyclic but the additivegroup ofFis usuallynotcyclic. WhenFcontainsFp, sincep= 0 inFpevery nonzeroelement ofFhas additive orderp, soFis not additively cyclic unless|F|is finite field is isomorphic toFp[x]/( (x))for some primepand somemonic irreducible (x)inFp[x]. a finite field. By Theorem ,Fhas orderpnfor some primepand positiveintegern, and there is a field embeddingFp groupF is cyclic by Lemma Let be a generator ofF . Evaluation at ,namelyf(x)7 f( ), is a ring homomorphism ev :Fp[x] Fthat fixesFp.

5 Since every1In a nonabelian finite group, all orders of elements don t have to divide the maximal order, , inS3the orders of elements are 1, 2, and FIELDS3number inFis 0 or a power of , ev is onto (0 = ev (0) and r= ev (xr) for allr 0).ThereforeFp[x]/ker ev =F. SinceFis a field, the kernel of ev is a maximal ideal inFp[x], so ker ev = ( (x)) for a monic irreducible (x) inFp[x]. Fields of size 9 that are of the formFp[x]/( (x)) needp= 3 and deg (x) = 2. Themonic irreducible quadratics inF3[x] arex2+ 1,x2+x+ 2, andx2+ 2x+ 2. InF3[x]/(x2+ 1),F3[x]/(x2+x+ 2),F3[x]/(x2+ 2x+ 2),xdoes not generate the nonzero elements in the first field but it generates the nonzeroelements in the second and third fields. So althoughF3[x]/(x2+ 1) is the simplest choiceamong these three examples, it snotthe one that would come out of the proof of when we look for a model of fields of order 9 asF3[x]/( (x)).Theorem does not assure us that a field of each prime power order exists.

6 It only tellsus thatifa field of orderpnexists then it is isomorphic toFp[x]/( (x)) for some irreducible (x) of degreeninFp[x]. Why is there an irreducible of each degree inFp[x]? In the nextsection we will show a field of each prime power order does exist and there is an irreducibleinFp[x] of each positive fields as splitting fieldsEach finite field is a splitting field of a polynomial depending only on the field s field of prime power orderpnis a splitting field overFpofxpn a field of orderpn. From the proof of Theorem ,Fcontains a subfieldisomorphic toZ/(p) =Fp. Explicitly, the subring ofFgenerated by 1 is a field of Fsatisfiestpn=t: ift6= 0 thentpn 1= 1 sinceF =F {0}is a multiplicativegroup of orderpn 1, and then multiplying through bytgives ustpn=t, which is also truewhent= 0. The polynomialxpn xhas every element ofFas a root, soFis a splittingfield ofxpn xover the fieldFp. Theorem every prime powerpn, a field of our cue from the statement of Lemma , letFbe a field extension ofFpover whichxpn xsplits completely.

7 General theorems from field theory guarantee thereis such a field. InsideF, the roots ofxpn xform the setS={t F:tpn=t}.This set has sizepnsince the polynomialxpn xis separable: (xpn x) =pnxpn 1 1 = 1sincep= 0 inF, soxpn xhas no roots in common with its derivative. It splits completelyoverFand has degreepn, so it haspnroots will showSis a subfield ofF. It contains 1 and is easily closed under multiplicationand (for nonzero solutions) inversion. It remains to showSis an additive group. Sincep= 0 inF, (a+b)p=ap+bpfor allaandbinF(the intermediate terms in (a+b)pcomingfrom the binomial theorem have integral coefficients(pk), which are all multiples ofpandthus vanish inF). Therefore thepth power mapt7 tponFis additive. The mapt7 tpnis also additive since it s then-fold composite oft7 tpwith itself and the composition4 KEITH CONRADof homomorphisms is a fixed points of an additive map are a groupunder addition, soSis a group under addition.

8 ThereforeSis a field of orderpn. Corollary every primepand positive integern, there is a monic irreducibleof degreeninFp[x], and moreover (x)can be chosen so that every nonzero element ofFp[x]/( (x))is congruent to a power Theorem , a fieldFof orderpnexists. By Theorem , the existence ofan abstract field of orderpnimplies the existence of a monic irreducible (x) inFp[x] ofdegreen, and from the proof of Theorem (x) generates the nonzero elementsofFp[x]/( (x)) since the isomorphism identifiesxmod (x) with a generator ofF . Appreciate the order in the logic behind Theorem and its corollary: to show we canconstruct a field of orderpnasFp[x]/( (x)) where deg (x) =n, the way we showed a (x)of degreenexists is byfirstconstructing an abstract fieldFof orderpn(using a splittingfield Construction ) and then provingFcan be made isomorphic to anFp[x]/( (x)).Remark is no formula for an irreducible ofeachdegree inFp[x].

9 Binomialpolynomialsxn aare reducible whenp|n. Trinomialsxn+axk+bwitha,b F pand0< k < nare often irreducible, but in some degrees they are all reducible: that occurs inF2[x] in degrees 8 and 13, inF3[x] in degrees 49 and 57, inF5[x] in degrees 35 and 70, andinF7[x] in degrees 124 and irreducible (x)inFp[x]of degreendividesxpn xand is fieldFp[x]/( (x)) has orderpn, sotpn=tfor alltinFp[x]/( (x)) (see the proofof Lemma ). In particular,xpn xmod (x), so (x)|(xpn x) inFp[x]. We saw in theproof of Theorem thatxpn xis separable inFp[x], so its factor (x) is separable. Example [x], the irreducible factorization ofx2n xforn= 1,2,3,4 is as x=x(x 1),x4 x=x(x 1)(x2+x+ 1),x8 x=x(x 1)(x3+x+ 1)(x3+x2+ 1),x16 x=x(x 1)(x2+x+ 1)(x4+x+ 1)(x4+x3+ 1)(x4+x3+x2+x+ 1).In each case the irreducibles of degreenappear in the factorization ofx2n x, whichTheorem guarantees must happen. That each factor occurs just once reflects the factthatxpn xis separable.

10 There are irreducible factors ofxpn xwith degree less thann,ifn >1; the irreducible factors ofxpn xinFp[x] turn out (Lemma below) to be theirreducibles inFp[x] of degree dividingnand each such factor appears writeFpnfor a finite field of orderpn. Features to keep in mind are it contains a unique subfield isomorphic toFp(namely the subfield generated by 1), [Fpn:Fp] =nby the proof of Theorem , it is a splitting field ofxpn xoverFpby the proof of Theorem , additivity oft7 tpnfollows from the binomial coefficients(pnk)being divisible bypfor1 k pn 1. In generalb(ab)=a(a 1b 1)for 1 b a, sok(pnk)=pn(pn 1k 1)when 1 k pn 1. Thusk(pnk)is divisible bypnand the first factorkis not divisible bypn, so(pnk)is divisible FIELDS5 Althoughxpn xhas degreepn, its splitting field overFphas degreen,notpn. That is notweird, becausexpn xis reducible (see Example ). The situation is similar toxm 1,which form >1 is reducible and its splitting field overQhas degree less finite fields of the same size are isomorphic to each finite field has prime power size, saypn.