Finite Fields This module deals with the existence and the structure of finite fields. Remarks 1. F x (f(x)) is a finite field when F is finite and f(x) is irreducible. Proposition 1. If F is a finite...

Finite Fields This module deals with the existence and the structure of finite fields. Remarks 1. F x (f(x)) is a finite field when F is finite and f(x) is irreducible. Proposition 1. If F is a finite fie p times ld then a smallest number p, which is necessarily prime, such that a F p a a + + a = 0 This number is called the characteristic of F and is denoted by ch(F). Proof Consi ? ? ?
 ··· { } a der any a F - 0 . Since F is finite the sequence a, a+a, a+a+a, , na, must include a repetition, say n a = m a where n > m. Therefore (n-m)a = 0. Let n be the smallest positive in ? ··· ··· { } ( ) a a b -1 -1 a a a -1 a a b teger such that n a = 1 Claim a, b F - 0 (n = n ) Proof n b = n ba a = ba (n a) by the general distributive law of a field. Hence n b = ba (0) = 0 and so n n . Intercha ? ? = b a a s1 nging a and b yields n n . Denote the common value of the n 's by p. Claim p is prime Proof If not 1 < r,="" s="">< p="" such="" that="" p="r" s.="" then="" 0="p1" =="" r="" (s1)="" thus="" r="" p="n" if="" s1="" 0="" -="?" =="" 1="" a="" contradiction.="" hence="" s1="0." but="" then="" s="" p="n" -="" another="" contradiction.="2" {="" }="" p="" {="" }="" proposition="" 2.="" the="" elements="" m="" 1="" m="0," 1,...,="" p-1="" constitutes="" a="" subfield="" of="" f="" and="" the="" mapping="" :="" z="" m="" 1="" m="0," 1,..,="" p-1="" m="" m="" 1="" is="" an="" isomorphism,="" i.e.="" is="" 1-1,="" onto="" and="" p="" p="" {="" }="" (n="" +="" m)="(n)" +="" (m)="" (n="" m)="(n)" (m)="" for="" all="" m,="" n="" z="" i.e.="" z="" and="" m="" 1="" m="0,...," p-1="" are="" algebraically="" identical.="" proof="" observe="" that="" m="" 1="" +="" n="" 1="(m+n)" 1="r" 1="" where="" m="" +="" n="q" p="" +="" r,="" 0="" r="">< p="" also="" (m="" 1)(n="" 1)="(mn)1" =="" r="" 1="" where="" m="" n="q" p="" +="" r="" 0="" r="">< p="" ;="" the="" operations="" are="" preserved.="" one-on=' ' '="" '="eness" and="" ontoness="" are="" obvious.="" p="" {="" }="" p="" remark="" 2.="" from="" this="" point="" on="" we="" "identify"="" z="" and="" m="" 1="" 0="" m="" p-1="" and="" regard="" z="" as="" a="" subfield="" of="" f.="" remark="" 3.="" we="" shall="" see="" that="" if="" f="" is="" finite="" then="" f="" is="" a="" power="" of="" the="" characteristic="" of="" f.="" the="=" value="" of="" the="" exponent="" is="" a="" "vector="" space"="" parameter.="" a="" couple="" of="" vector="" space="" essentials="" definition="" 1.="" a="" vector="" space="" v="" over="" a="" field="" f="" is="" a="" set="" v="" together="" with="" two="" operations:="" +:="" v="" xv="" v="" (c="" alled="" vector="" addition)="" (x,="" y)="" x="" +="" y="" and="" :="" f="" x="" v="" v="" (called="" scalar="" multiplication)="" (="" ,="" x)="" x="" such="" that="" (1)="" (v,="" +)="" is="" an="" abelian="" group="" (2)="" (="" )="" a="" a="" aß="" i="" i="" (="" )="" x="(" x)="" ,="" f="" x="" v="" (3)="" +="" x="x" +="" x="" ,="" f="" x="" v="" a="" ß="" a="" ß="" a="" ß="" a="" ß="" a="" ß="" i="" i="" i="" i="" i="" i="" 3="" (x="" +="" y)="x" +="" y="" f="" x,="" y="" v="" (4)="" 1="" x="x" x="" v="" a="" a="" a="" a?="" i="" i="" i="" i="" remark="" 4.="" we="" shall="" dispense="" with="" the="" "dot",="" i.e.="" we'll="" write="" x="" instead="" of="" x.="" excercise="" 1:="" (submit="" this="" one)="" a)="" prove:="" 0="" x="0," where="" the="" zero="" on="" the="" left="" is="" the="" additive="" identity="" a="" ai="" of="" f="" and="" the="" zero="" on="" the="" right="" is="" the="" additive="" identity="" of="" v="" b)="" prove:="" (-="" 1)="" x="-x" x="" v="" where="" -x="" is="" the="" additive="" inverse="" of="" x="" in="" (v,="" +)="" c)="" prove:="" 0="0" a="" a="" f="" 1="" n="" 1="" n="" n="" i="" i="" i="1" definition="" 2.="" v="" is="" a="" finite="" dimensional="" vector="" space="" over="" f="" if="" and="" only="" if="" a="" finite="" set="" of="" vectors,="" say="" x="" ,..,="" x="" such="" that="" x="" v="" a="" ,="" ,="" a="" f="" such="" that="" x="a" x="" (linear="" combination;="" lc).="" th="" ···="" e="" vectors="" x="" x="" are="" said="" to="" span="" v="" and="" x="" ,="" ,="" 1="" n="" {="" 1="" n="" x="" }="" is="" a="" spanning="" set.="" ···="" ···="" {(="" )="" }="" {="" }="" {="" }[="" ]="" 3="" 2="" 3="" example="" 1.="" 1,="" 0,="" 0="" ,="" (0,="" 1,="" 0),="" (0,="" 0,="" 1)="" spans="" r="" (3="" -="" dimensional="" euclidean="" space)="" example="" 2.="" 1,="" x,="" x="" spans="" 0,="" 1="" x="" (x="" +="" x="" +="" 1)="" [="" ]="" remark="" 5.="" in="" the="" previous="" two="" examples="" the="" coefficients="" required="" to="" write="" a="" particular="" x="" as="" a="" lc="" of="" the="" spanning="" vectors="" are="" seen="" to="" be="" unique="" -="" why?="" exercise="" 5.="" if="" f="" is="" any="" field="" then="" f="" x="" is="" a="" vect="" {="" }="" 1="" n="" n="" i="" i="" i="1" or="" space="" over="" f.="" prove="" it="" is="" not="" finite="" dimensional.="" definition="" 3.="" the="" set="" x="" ,..,="" x="" v="" is="" linearly="" independent="" (li)="" if="" and="" only="" if="" x="0" =="" 0="" i.="" otherwise="" the="" set="" is="" a="" a="" i="" {="" }="" 1="" 2="" n="" 2="" n="" called="" linear="" dependent="" (ld).="" observation="" 1.="" 0="x" ,="" x="" ..,="" x="" is="" ld="" proof="" 1="" 0="" +="" 0="" x="" +="" +="" 0="" x="0." ··="" {="" }="" n="" i="" i="" i="1" 1="" n="" proposition="" 3.="" the="" coefficients="" in="" the="" expression="" x="" are="" unique="" if="" and="" only="" if="" x="" ,="" ,="" x="" is="" li.="" a="" ··="" 4="" (="" )="" {="" }="" (="" )="" {="" }="" n="" n="" n="" 1="" i="" i="" i="" i="" i="1" i="1" i="1" 1="" n="" i="" i="" i="" 1="" n="" 1="" n="" proof="" of="" course="" x="x" -="" x="0." thus="" if="" x="" ,="" x="" is="" li,="i.e." uniqueness="" follows.="" conversely="" if="" x="" ,="" ,="" x="" is="" ld="" then="" ,..,="" not="" all="" 0="" such="" that="" a="" ß="" a="" ß="" i="" i="" a="" ß="" a="" a="" ··="" ··="" (="" )="" n="" i="" i="" i="1" n="" n="" i="" i="" i="" i="" i="" i="1" i="1" x="0." then="" +="" x="x" ,="" i.e.="" the="" coefficients="" are="" not="" unique.="" a="" a="" a="" a="" {="" }="" {="" }="" {="" }="" {="" }="" 1="" 2="" m="" 1="" 1="" proposition="" 4.="" if="" v="" 0="" and="" s="x" ,="" x="" ,="" ,="" x="" is="" a="" spanning="" set="" for="" v="" then="" s="" b="" -="" a="" li="" spanning="" set.="" proof="" (by="" induction="" on="" m)="" m="1:" if="" s="x" is="" a="" spanning="" set="" for="" v="" and="" v="" 0="" then="" x="" 0="" so="" suppose="" ··="" (="" )="" (="" )="" {="" }="" 1="" -1="" -1="" 1="" -1="" 1="" 1="" 1="" 1="" s="" is="" ld,="" i.e.="" 0="" such="" that="" x="0." then="" x="0" =="" 0="" i.e.="" x="1" x="x" =="" 0="" thus="" x="" is="" li.="" suppose="" the="" result="" is="" true="" for="" s="m" and="" consider="" the="" case="" where="" s="a" a="" a="" a="" a="" a="" a="" {="" }="" 1="" 2="" m="" m+1="" 1="" m+1="" 1="" 1="" 2="" 2="" m="" m="" m+1="" m+1="" j="" m="" +="" 1="" i.e.="" s="x" ,="" x="" ,="" x="" ,="" x="" case="" (a)="" s="" is="" li="" -="" then="" done!="" case="" (b)="" s="" is="" ld:="" so="" ,="" not="" all="" sero="" such="" that="" x="" +="" x="" +="" +="" x="" +="" x="0" now="" 0="" so="" a="" a="" a="" a="" a="" a="" a="" ··="" ··="" ···="" m+1="" 1="" j="" j="" i="" i="" i="1" i="" j="" x="x" a="" a="" -="" {="" 1="" 2="" j="" j="" m="" }="" 1="" m+1="" m+1="" 1="" 1="" i="" j="" j="" i="1" i="" j="" 1="" i="" j="" i="" i="" j="" 1="" j="" j="" i="" j="" claim="" s="x" ,="" x="" ,="" ,="" x="" 1,="" x="" 1,="" ,="" x="" 1="" spans="" v="" indeed,="" if="" x="" v="" ,="" ,="" such="" that="" x="x" =="" x="" +="" x="x" +="" x="+" i="" i="" j="" i="" i="" j="" i="" ß="" ß="" ß="" ß="" ß="" ß="" ß="" a="" a="" ß="" ß="" a="" a="" -="" -="" '="" ··="" -="" +="" ··="" +="" ··="" (="" )i="" i="" x="" thus,="" by="" the="" induction="" hypothesis,="" s="" s="" '="" b="" where="" b="" is="" a="" li="" spanning="" set="" 5="" definition="" 4="" and="" remark="" 6.="" a="" li="" spanning="" set="" is="" called="" a="" basis.="" the="" proposition="" says="" that="" every="" spanning="" set="" of="" a="" finite="" dimensional="" vector="" space="" contains="" a="" basis.="" the="" proof="" shows="" that="" if="" the="" spanning="" set="" is="" ld="" it="" can="" be="" "pruned="" down"="" to="" a="" basis.="" our="" next="" objective="" is="" to="" prove="" that="" any="" two="" bases="" have="" equal="" size.="" {="" }="" {="" }="" {="" }="" 1="" 2="" m="" 1="" 2="" n="" i="" j="" j="" proposition="" 5.="" if="" s="" is="" a="" spanning="" set="" for="" v="" and="" l="" is="" a="" li="" set="" in="" v="" then="" l="" s="" .="" proof="" let="" s="y" ,="" y="" ,="" ,="" y="" and="" l="x" ,="" x="" ,="" x="" .="" claim="" if="" l="" s="" and="" x="" l="" -="" s="" then="" y="" s="" -="" l="" such="" that="" s="" -="" y="" =="" ··="" ··="" {="" }i="" x="" is="" a="" spanning="" set="" for="" v.="" {="" }="" (="" )="" i="" i="" k="" i="" k="" k="" f="" k="" k="" i="" k="" f="" proof="" consider="" any="" x="" l="" -="" s.="" since="" l="" is="" li,="" x="" 0.="" then="" non="" zero="" ,="" k="" f="" 1,="" 2,="" m="" such="" that="" x="y" .="" now="" not="" all="" the="" y="" can="" be="" in="" l="" for="" then="" y="" +="" -1="" x="0" contradicts="" linear="" k="" k="" a="" a="" a="" ··="" (="" )="" {="" }="" {="" }="" j="" 1="" j="" j="" k="" k="" j="" k="" j="" k="" f="" j="" i="" independence="" of="" l.="" thus="" y="" s="" -="" l="" such="" that="" y="(" y="" +="" x="" )="" but="" then="" every="" lc="" of="" vectors="" in="" s="" can="" be="" rewritten="" as="" a="" lc="" of="" the="" vectors="" in="" s="" -="" y="" x="" .="" exercise="" 3.="" a="" a="" -="" -="" {="" 1="" 2="" m}="" m+1="" 1="" m="" now="" suppose="" m="">< n.="" it="" follows="" by="" induction="" that="" x="" ,="" x="" ,="" x="" is="" a="" spanning="" set="" for="" v="" so="" that="" x="LC" of="" x="" ,="" ,="" x="" -="" this="" contradicts="" li="" of="" l.="" note:="" this="" proof="" uses="" a="" "replacement"="" procedure.="" ··="" ··="" 1="" 2="" 1="" 2="" corollary="" 2="" and="" definition="" 5.="" any="" two="" bases="" for="" v="" have="" the="" same="" size.="" that="" size="" is="" referred="" to="" as="" the="" dimension="" of="" v="" and="" is="" denoted="" by="" dim="" v.="" proof="" suppose="" b="" and="" b="" are="" bases.="" since="" b="" is="" li="" and="" b="" i="" 1="" 2="" 2="" 1="" 2="" 1="" s="" a="" spanning="" set="" b="" b="" .="" likewise,="" since="" b="" is="" li="" and="" b="" is="" a="" spanning="" set="" b="" b="" .="=" exercise="" 4.="" (submit="" d)="" suppose="" v="" is="" finite="" dimensional="" with="" dimv="n." a)="" prove:="" if="" b="" is="" li="" and="" b="n" then="" b="" is="" a="" basis="" for="" v.="" b)="" prove:="" if="" s="" is="" a="" spanning="" set="" for="" v="" and="" s="n" then="" s="" is="" a="" basis="" for="" v.="" c)="" prove:="" if="" l="" v="" is="" li="" then="" a="" basis="" b="" for="" v="" such="" that="" l="" b.="" d)="" prove:="" if="" w="" is="" also="" a="" vector="" space="" over="" f="" with="" dim="" v="n" then="" v="" and="" w="" are="" (vector="" space)="" isomorphic="" ie.="" 6="" {="" }="" {="" }="" 1="" n="" 1="" 2="" n="" n="" n="" 1="" i="" i="1" i="1" t:="" v="" w="" such="" that="" t="" is="" a="" bijection="" and="" t="" (="" x+y)="T(x)" +="" t(y)="" f,="" x,="" y="" v.="" hint="" let="" x="" ,="" ,="" x="" be="" a="" basis="" for="" v="" and="" w="" ,="" w="" ,="" ,="" w="" be="" a="" basis="" for="" w.="" define="" t="" x="a" a="" a="" a="" ··="" ··="" i="" ai="" w="" p="" k="" theorem="" 1.="" if="" f="" is="" a="" finite="" field="" with="" chf="p" then="" f="" is="" a="" finite="" dimensional="" vetor="" space="" over="" z="" .="" furthermore,="" if="" dimf="k" then="" f="p" proof="" the="" vector="" space="" sum="" is="" just="" the="" sum="" in="" f;="" scalar="" multip="" (="" )="" lication="" is="" given="" by="" m="" a="m1" a="" where="" the="" multiplication="" on="" the="" right="" is="" field="" multiplication.="" the="" properties="" of="" a="" vector="" space="" are="" easy="" to="" verify.="" since="" f="" is="" finite="" a="" finite="" spanning="" set="" for="" f="" so="" ·="" {="" }="" 1="" 2="" k="" k="" i="" i="" i="1" i="" that="" f="" is="" finite="" dimensional.="" if="" ,="" ,="" ,="" is="" a="" basis="" then="" the="" elements="" of="" f="" are="" uniquely="" represented="" in="" the="" form="m" as="" there="" are="" p="" choices="" for="" each="" m="" it="" follows="" that="" a="" a="" a="" a="" a="" ··="" ·="" k="" f="p" [="" ]="" (="" )="" {="" }="" (="" )="" {="" }[="" ]="" (="" )="" 2="" 3="" 2="" 2="" 1="" 2="" 3="" 3="" 1="" 2="" 3="" example="" 2="" revisited.="" the="" elements="" 1,="" x="" and="" x="" constitute="" a="" basis="" for="" f="" x="" f(x)="" where="" f="Z" =="" 0,="" 1="" and="" f="" x="x" +="" x="" +="" 1,="" i.e.="" m="" 1="" +="" m="" x="" +="" m="" x="" runs="" through="" all="" of="" 0,="" 1="" x="" x="" +="" x="" +="" 1="" as="" m="" ,="" m="" and="" m="" run="" {="" }="" {="" }[="" ]="" (="" )="" 2="" 3="" 3="" through="" z="0," 1="" .="" also="" 0,1="" x="" x="" +="" x="" +="" 1="2" =="" 8="" as="" we="" have="" already="" seen.="" k="" p="" remark="" 7.="" if="" f="" and="" g="" are="" two="" finite="" fields="" such="" that="" f="G" then="" with="" f="p" and="" g="q" it="" follows="" that="" p="q" and="" k="." hence="" f="" and="" g="" are="" k-dimensional="" vector="" spaces="" over="" z="" and="" are="" therefore="" ="" ="" vector="" space="" isomorphic;="" however="" the="" isomorphism="" doesn't="" necessarily="" preserve="" "field"="" multiplication.="" as="" it="" happens="" f="" and="" g="" are="" "field"="" isomorphic="" but="" we="" require="" some="" additional="" insights="" before="" we="" prove="" this="" fact.="" one="" fundamental="" insight="" has="" already="" been="" discovered="" in="" module="" iii.="" 7="" {="" }="" {="" }="" k="" 1="" p="" 2="" theorem="" 2.="" if="" f="" is="" a="" finite="" field="" then="" the="" multiplicative="" group="" f="" f="" -="" 0="" is="" cyclic;="" i.e.="" f="" such="" that="" f="1" =="" ,="" ,="" ,="" .="" exercise="" 5.="" (submit="" this="" one)="" a)="" prove="" that="" the="" number="" of="" primitiv="" a="" a="" a="" a="" *="" *="" -="?" ··="" ="" (="" )="" {="" }="" k="" t="" k="" e="" elements="" (i.e.="" generators)="" in="" f="" is="" just="" p="" 1="" .="" if="" is="" a="" given="" primitive="" then="" gcd(t,="" p="" 1)="" 1="" is="" the="" collection="" of="" all="" primitives.="" b)="" prove="" is="" a="" pr="" a="" a="" a="" *="" -="" -="k" p="" 1="" k="" q="" imitive="" if="" and="" only="" in="" primes="" q="" if="" q="" p="" 1="" then="" 1="" a="" -="" -="" {="" }[="" ]="" (="" )="" {="" }[="" ]="" (="" )="" 3="" 4="" 3="" 2="" 4="" 3="" 2="" exercise="" 6.="" consider="" 0,="" 1="" x="" x="" +="" x="" +="" 1="" .="" how="" many="" primitives="" does="" this="" field="" have?="" find="" them.="" example="" 3.="" consider="" 0,="" 1="" x="" x="" +="" x="" +="" x="" +="" x="" +="" 1="" claim="" this="" is="" a="" field="" as="" x="" +="" x="" +="" x="" +="" x="" +="" 1="" is="" irreducible.="" pro="" (="" )(="" )="" 2="" 2="" 4="" 3="" 2="" 2="" 3="" of="" since="" neither="" 0="" nor="" 1="" is="" a="" root="" x+1="" and="" x="" are="" not="" factors.="" consider="" x="" +="" x="" +="" x="" +="" x="" +="x" +="" x="" +="" x="" +="" x="" +="" 1="" since="" 1,="" x,="" x="" ,="" x="" is="" a="" basis="" we="" get="1" i.e.="=" a="" ß="" ß="" ß="" 1="" thus="" +="1," i.e.="" +="1" we="" logically="" assume="1," =="" 0.="" then="" +="" +="1" but="" +="" +="0" 1.="" thus="" the="" polynomial="" is="" irreducible.="" a="" ß="" a="" a="" a="" ß="" a="" ß="" (="" )="" 4="" 4="" 3="" 2="" 5="" 4="" 3="" 2="" 3="" 2="" 3="" 2="" since="" f="2" -="" 1="15" there="" are="" 15="8" primitives.="" observe="" x="x" +="" x="" +="" x="" +="" 1="" so="" x="x" +="" x="" +="" x="" +="" x="x" +="" x="" +="" x="" +="" 1="" +="" x="" +="" x="" +="" x="1" *="" 2="" 2="" 3="" 3="" 2="" 4="" 4="" 5="" 4="" 3="" 2="" thus="" ord="" (x)="5." next="" consider="" x="" +="" 1:="" (x="" +="" 1)="x" +="" 1="" (x="" +="" 1)="x" +="" x="" +="" x="" +="" 1="x" (x="" +="" 1)="x" +="" x="1" +="" x="" +="" x="" +="" x="" +="" 1="" 3="" 2="" 5="" 3="" 2="x" +="" x="" +="" x="" (x="" +="" 1)="x" +="" x="" +="" 1="" 1="" thus="" (ord)="" (x+1)="15." 8="" (="" )(="" )="" (="" )="" (="" )="" 2="" 2="" 4="" 3="" 2="" 7="" 2="" 3="" 2="" 2="" 8="" 3="" 3="" 8="" 11="" 3="" the="" other="" primitives="" are="" (x="" +="" 1)="x" +="" 1="" (x="" +="" 1)="x" +="" x="" +="" x="" (x="" +="" 1)="x" +="" 1="" x="" +="" x="" +="" 1="x" +="" x="" +="" 1="" (x="" +="" 1)="x" +="" 1="" (x+1)="x" +="" 1="" x="" +="" 1="x" +="" x="" +="" 1="" 13="" 2="" 14="" 3="" (x="" +="" 1)="x" +="" x="" and="" (="" x="" +="" 1)="x" +="" x.="" (="" )="" [="" ]="" k="" k="" k="" p="" 1="" p="" 2="" p="" i="" i="" 0="" p="" corollary="" 2.1="" every="" element="" of="" f="" is="" a="" root="" of="" x="" 1;="" in="" fact="" x="" x="x" x="" -="" where="" is="" a="" primitive.="" remark="" 8.="" the="" previous="" corollary="" shows="" that="" for="" each="" f="" a="" monic="" polynomial="" in="" z="" x="" a="" a="" ß="" *="" -="" -="*" -="" -="" p="" ,="" i.e.="" with="" coefficients="" from="" z="" ,="" that="" satisfies.="" ß="" definition="" 6.="" if="" f="" then="" the="" minimal="" polynomial="" of="" is="" the="" monic="" polynomial="" m(x)="" z="" x="" p="" [="" ]="" of="" smallest="" degree="" having="" as="" a="" root.="" remark="" 9.="" that="" m="" (x)="" is="" unique="" is="" left="" to="" exercise="" 7.="" theorem="" 3.="" if="" 0="" a="" ß="" ß="" ß="" ß="" [="" ]="" [="" ]="" k="" k="" p="" 1="" p="" p="" 1="" p="" then="" m="" (x)="" x="" -="" 1.="" furthermore="" m="" (x)="" is="" irreducible="" in="" z="" x="" .="" proof="" write="" x="" -="" 1="q" (x)="" m(x)="" +="" r="" (x)="" deg="" r="">< deg="" m="" in="" z="" x="" by="" the="" division="" algorithm.="" but="" r(="" )="0" now="" r(x)="" cannot="" be="" a="" non-ze="" ß="" ß="" ß="" ß="" -="" -="" (="" )="" (="" )="" ro="" constant="" and,="" since="" m="" (x)="" has="" the="" minimum="" degree="" such="" that="" m="0," r="" must="" be="" the="" zero="" polynomial.="" next="" suppose="" m="" (x)="P(x)" q="" (x)="" where="" p="" and="" q="" are="" monic="" and="" of="" positive="" degree.="" but="" 0="M" ß="" ß="" ß="" ß="" ß="" ß="" (="" )="" (="" )="" (="" )="" (="" )="P" q="" in="" f="" so="" p(="" )="0" or="" q="0" -="" which="" contradicts="" the="" definition="" of="" m="" x="" .="" ß="" ß="" ß="" ß="" ß="" [="" ]="" [="" ]="" p="" p="" exercise="" 8.="" (submit="" this="" one)="" a)="" suppose="" f(x)="" z="" x="" and="" f(="" )="0;" prove="" m="" f="" (hint:="" immitate="" the="" proof="" of="" the="" previous="" theorem).="" b)="" prove:="" m="" is="" unique="" c)="" prove:="" if="" f(x)="" z="" x="" ,="" is="" irreduci="" a="" a="" a="" ble,="" monic="" and="" f(="" )="0" then="" f(x)="M" (x)="" d)="" what="" is="" the="" minimal="" polynomial="" of="" 0?="" a="" a="" 9="" our="" next="" major="" task="" is="" to="" prove="" that="" any="" two="" finite="" fields="" having="" the="" same="" number="" of="" elements="" are="" field="" isomorphic="" but="" first="" we="" require="" lemmas,="" the="" second="" of="" which="" is="" essential="" for="" the="" definition="" [="" ]="" p="" of="" the="" isomorphism.="" our="" first="" lemma="" is="" a="" very="" useful="" technical="" lemma="" and="" is="" concerned="" with="" the="" coefficients="" of="" the="" polynomial="" (f(x))="" where="" f(x)="" f="" x="" and="" chf="p." [="" ]="" [="" ]="" p="" p="" p="" n="" n="" i="" p="" p="" p="" i="" i="" i="" i="0" i="0" p="" p="" lemma1.="" let="" f="" be="" a="" finite="" field="" with="" chf="p" (1)="" if="" g(x),="" h(x)="" f="" x="" then="" (g(x)="" +="" h(x))="(g(x))" +="" (h(x))="" (2)="" if="" f(x)="a" x="" then="" (f(x))="a" (x="" )="" .="" (3)="" if="" f="Z" and="" f(x)="" z="" x="" then="" (="" )="" p="" p="" p="" p="" i="" p-i="" i="0" (f(x))="f(x" )="" proof="" (1)="" it="" is="" a="" technical="" exercise="" to="" prove="" p="" g(x)="" +="" h(x)="(g(x))" (h(x))="" i="" p="" p="" since="" p="" for="" 1="" i="" p="" -="" 1="" it="" follows="" that="" 1="0" for="" i="1,..," p="" i="" i="" =="?" p="" p="" -1="" and="" the="" result="" follows.="" (2)="" the="" use="" of="" induction="" and="" (1)="" yields="" (2).="" (3)="" in="" this="" case="" a="a" a="" z="" (euler's="" theorem).="" so="" the="" conclusion="" follows="" from="" (2).="" [="" ]="" k="" lemma="" 1.="" suppose="" f="G" =="" p="" ,="" is="" a="" primitive="" of="" f="" an="" p="" d="" m="" (x)="" z="" x="" is="" the="" minimal="" polynomial="" of="" .="" then="" (1)="" g="" such="" that="" m="" (x)="" is="" the="" minimal="" polynomial="" of="" ,="" (2)="" every="" root="" of="" m="" (x)="" in="" g="" a="" a="" a="" a="" a="" ß="" ß="" *="" [="" ]="" (="" )="" k-1="" i="" k-1="" p="" p="" p="" i="1" p="" ,="" in="" particular="" the="" of="" (1),="" is="" a="" primitive="" in="" g="" and="" (3)="" the="" roots="" of="" m="" (x)="" in="" f="" are="" given="" by="" ,="" ,...,="" and="" m="" (x)="(x" -="" )="" in="" f="" x="" ;="" likewise="" the="" roots="" of="" m="" x="" in="" g="" are="" given="" by="" ,="" ,...="" a="" a="" a="" ß="" a="" a="" a="" a="" ß="" ß="" *="" (="" )="" [="" ]="" 1="" i="" k-1="" p="" i="1" ,="" and="" m="" (x)="x" -="" in="" g="" x="" .="" k="" p="" ß="" ß="" a="" -="" [="" ]="" k="" k="" p="" 1="" p="" p="" 1="" proof="" (1)="" recall="" from="" theorem="" 3="" that="" m="" (x)="" x="" 1.="" thus="" n(x)="" z="" x="" such="" that="" x="" -="" 1="M" (x)="" n(x)="" now,="" focusing="" on="" g,="" it="" follows="" by="" corollary="" 2.1="" that="" every="" element="" of="" g="" is="" a="" root="" of="" x="" a="" a="" -="" -="" *="" -="" (="" )="" (="" )="" k="" p="" 1="" -="" 1.="" hence="" if="" g="" then="" m="" n="0" so="" that="" either="" is="" a="" root="" of="" m="" (x)="" or="" is="" a="" root="" of="" n(x).="" by="" theorem="" 3="" of="" module="" v="" n(x)="" can="" have="" no="" more="" that="" deg="" n="" roots="" in="" g.="" but="" de="" ß="" ß="" ß="" ß="" ß="" a="" a="" -="" *="" k="" k="" g="" n="p" 1="" -="" deg="" m="">< p="" 1="" so="" g="" such="" that="" is="" a="" root="" of="" m="" (x).="" -="" -="" a="" ß="" ß="" a="" 10="" p="" [="" ]="" (2)="" let="" denote="" an="" arbitrary="" root="" of="" m="" (x)="" in="" g.="" as="" m="" (x)="" and="" m="" (x)="" are="" irreducible="" in="" z="" x="" by="" theorem="" 3="" and="" m="" (x)="" m="" (x)="" by="" exercise="" 7="" c)="" it="" follows="" that="" m="" (x)="" is="" the="" minimal="" polynomial="" of="" .="" th="" a="" a="" a="" a="" ord="" ord="" k="" k="" k="" k="" k="" us,="" by="" a)="" of="" exercise="" 8.="" m="" (x)="" x="" 1="" and="" so="" 1="" 0="" because="" m="" (="" )="0." but="" ord="p" 1="" so="" p="" 1="" ord="" finally="" then="" ord="" p="" 1="" because="" g="p" 1="" and="" ord="p" 1="" (="" a="" a="" a="" a="" a="" *="" -="" -="-" -="" -="" -="" -="" i="" 2="" k-1="" p="" p="" p="" p="" p="" p="" p="" 3)="" now="" lemma="" 1="" (3)="" yields="" (m="" (x))="M" (x="" )="" so="" the="" fact="" that="" m="" (="" )="0" implies="" that="" m="" (="" )="0." thus="" by="" induction.="" m="" (="" )="0" i="" 0.="" consider="" the="" powers="" ,="" ,="" ,..,="" ;="" we="" claim="" that="" a="" a="" a="" a="" a="" a="" a="" a="" =="" a="" a="" a="" a="" i="" j="" j="" i="" p="" p="" p="" p="" k="" j="" i="" j="" i="" k="" they="" are="" distinct.="" indeed,="" if="where" 0="" i="" j="" k-1="" then="1." but="" then="" p="" 1="ord" p="" p="" -="" a="" contradiction="" since="" p="" p="">< p="" -="" 1.="" a="" a="" a="" a="" -="=" =="" -="" -="" -="" k-1="" p="" p="" next="" realize="" that="" the="" distinctness="" implies="" that="" x="" -="" ,="" x="" -="" ,...,="" x="" -="" are="" pairwise="" relatively="" prime="" irreducible="" polynomials,="" each="" of="" which="" divides="" m="" (x)="" by="" theorem="" 3="" of="" module="" v.="" thus="" a="" a="" a="" a="" i="" k-1="" p="" 1="0" (x="" -="" )="" m="" (x).="" a="" a="" {="" }="" 2="" k="" k="" 0="" k="" i="" i="" i="0" of="" course,="" the="" required="" conclusion="" follows="" from="" the="" fact="" that="" deg="" m="" k.="" to="" see="" this="" observe="" that="" 1,="" ,="" ,..,="" is="" ld="" in="" f="" (since="" dimf="k)," i.e.="" a="" ,..,="" a="" such="" that="" a="0" and="" not="" all="" a="" i="" a="" a="" a="" a="" a="?" =="" 0.="" thus="" a="" polynomial="" of="" deg="" k="" that="" has="" as="" a="" root.="" but="" then="" deg="" m="" k="" follows.="" the="" argument="" for="" is="" identical="" to="" this="" one.="" a="" a="" ß="" =="2" k-1="" p="" p="" p="" exercise="" 9.="" (submit="" a;="" b="" is="" for="" extra="" credit)="" a)="" with="" f="" as="" in="" lemma="" 2="" and="" a="" primitive="" of="" f="" ,="" prove="" that="" ,="" ,..,="" are="" also="" primitives.="" b)="" suppose="" f="" is="" finite="" with="" chf="p" and="" con="" a="" a="" a="" a="" *="" sider="" m="" (x)="" z="" x="" p="" [="" ]="" where="" f="" .="" prove:="" if="" f="" is="" a="" root="" of="" m="" (x)="" then="" ord="ord" a="" a="" *="" *="" 11="" [="" ]="" [="" ]="" k="" p="" theorem="" 4.="" if="" f="G" =="" p="" then="" f="" and="" g="" are="" field="" isomorphic.="" more="" specifically,="" if="" is="" a="" primitive="" in="" f="" with="" minimal="" polynomial="" m="" (x)="" z="" x="" and="" is="" a="" root="" of="" m="" (x)="" in="" g="" then="" a="" a="" a="" ß="" *="" j="" j="" k="" :="" f="" g="" 0="" if="" a="0" a="" (a)="if" a="," 0="" j="" p="" 2="" is="" a="" bijection="" such="" that="" (="" )="" (a="" +="" b)="(a)" +="" (b)="" (="" )="" (ab)="(a)" (b)="" i="" ii="" ß="" a="" =="-" ·="" i="" j="" k="" proof="" consider="" as="" given.="" claim="" 1.="" is="" 1-1:="" suppose="" a="" b.="" if="" a,="" b="" f="" then="" a="and" b="where" i="" j="" and="" 0="" i,="" j="" p="" 2.="" but="" then,="" since="" is="" a="" primitive="" of="" g="" by="" lemma="" 2(2)="" (a)="?" a="" a="" ß="" *="" *="" =="-" i="" j="" j="" j="" j="" k="(b)" if="" a="0" and="" b="then" (a)="0" =="" (b)="" claim="" 2.="" is="" onto:="" consider="" c="" g.="" then="" either="" c="0" or="" c="where" 0="" j="" p="" 2="" by="" lemma="" 2(2).="" thus="" (0)="0" =="" c="" ß="" ß="" a="" ß="" ß="" =="-" j="" j="" or="" (="" )="=" c.="" a="" ß="" (="" )="" (="" )="" (="" )="" (="" )="" (="" )="" (="" )="" (="" )="" (="" )="" (="" )="" k="" k="" i="" j="" i+j(mod="" p="" 1)="" i="" +="" j(mod="" p="" 1)="" i="" j="" i="" j="" claim="" 3.="" satisfies="" ):="" consider="=" =="Also" 0="" a="0" =="" 0="0" a="0" a="" ii="" a="" a="" a="" ß="" ß="" ß="" a="" a="" -="" -="" ·="" ·="" 12="" (="" )="" (="" )="" (="" )="" (="" )="" (="" )="" i="" j="" i="" j="" claim="" 4.="" satisfies="" )="" :="" first="" consider="" 0="" +="" b="b" =="" 0="" +="" b="0" +="" b="" next="" suppose="" a,="" b="" 0="" but="" a+b="0." then="" a="," b="so" that="" +="0" and="" is="" a="" root="" of="" f(x)="" i="" a="" a="" a="" a="" a="" [="" ]="" i="" j="" p="" i="" j="" i="" j="" i="" j="x" +="" x="" z="" x="" .="" now="" it="" follows="" by="" exercise="" 7(a)="" that="" m="" (x)="" f(x)="x" +="" x="" .="" but="" m="" (="" )="0" by="" lemma="" 2(2)="" so="" 0="f(" )="+" and="" so="" (a="" +="" b)="(0)" =="" 0="+" =="" (a)="" a="" a="" ß="" ß="" ß="" ß="" ß="" ß="" +="" (b)="" exercise="" 9.="" (extra="" credit)="" prove="" )="" for="" the="" case="" a,="" b,="" and="" a="" +="" b="" 0.="" remark="" 9.="" the="" existence="" of="" the="" field="" isomorphism="" means="" that="" f="" and="" g="" are="" "algebraically"="" identical.="" indeed,="" the="" function="" mer="" i="" -1="" ely="" renames="" the="" elements="" of="" f,="" e.g.="" (0)="" is="" the="" additive="" identity="" of="" g,="" (-a)="" is="" the="" additive="" inverse="" of="" (a)="" in="" g,="" (1)="" is="" the="" multiplicative="" identity="" in="" g="" and="" (a="" )="" is="" the="" multiplicative="" inver="" se="" of="" (a)="" when="" a="" 0.="" [="" ]="" (="" )="" k="" p="" j="" j="" k="" corollary="" 4.1="" if="" f="p" ,="" is="" a="" primitive="" of="" f="" and="" m="" (x)="" is="" the="" minimal="" polynomial="" of="" then="" :="" f="" z="" x="" m="" (x)="" ˆ="" 0="" if="" a="0" a="" (a)="ˆ" x="" if="" a="," 0="" j="" p="" 2="" is="" a="" f="" a="" a="" a="" a="" a="" *="" =="-" [="" ]="" (="" )="" [="" ]="" (="" )="" [="" ]="" (="" )="" k="" p="" p="" p="" ield="" isomorphism.="" proof="" it="" is="" enough="" to="" note="" that="" z="" x="" m="" (x)="p" and="" m="" (x)="0" (mod="" m="" (x)),="" i.e.="" x="" is="" a="" root="" of="" m="" in="" z="" x="" m="" (x)="" for="" then="" the="" result="" follows="" from="" theorem="" 5="" with="" g="Z" x="" m="" (x)="" and="x." a="" a="" a="" a="" a="" a="" ß="" [="" ]="" (="" )="" 4="" 3="" 2="" 2="" 4="" 3="" 2="" x="" example="" 4.="" consider="" f="Z" x="" x="" +="" x="" +="" x="" +="" x="" +="" 1="" of="" course="" m="" (y)="y" +="" y="" +="" y="" +="" y="" +="" 1="" is="" the="" minimal="" polynomial="" of="" the="" element="" x="" f.="" howev="" er="" x="" is="" not="" a="" primitive="" of="" f="" for="" as="" 5="" it="" was="" shown="" in="" example="" 3,="" x="1." it="" was="" also="" shown="" in="" that="" example="" that="" x="" +="" 1="" is="" a="" primitive.="" 13="" (="" )="" (="" )="" (="" )="" (="" )="" 4="" 4="" 3="" 2="" 3="" 3="" 2="" 4="" 3="" 4="" 3="" observe="" that="" x="" +="" 1="x" +="" 1="x" +="" x="" +="" x="" and="" x="" +="" 1="x" +="" x="" +="" x="" +="" 1="" so="" x="" +="" 1="" +="" x+="" 1="" +="" 1="0" but="" it="" is="" easily="" shown="" that="" y="" +="" y="" +="" 1="" is="" irreducible="" in="" z="" [="" ]="" [="" ]="" (="" )="" [="" ]="" (="" )="" 2="" 4="" 3="" x+1="" 4="" 3="" 2="" 4="" 3="" 2="" 2="" y="" so="" it="" follows="" by="" exercise="" 7="" (c)="" that="" m="" (y)="y" +="" y="" +="" 1="" thus="" :="" z="" x="" x="" +="" x="" +="" x="" +="" x="" +="" 1="" z="" y="" y="" +="" y="" +="" 1="" a="" (="" )="" i="" j="" 0,="" if="" a="0" a="y" ,="" if="" a="(x" +="" 1)="" ,="" 0="" j="" 1="" is="" an="" isomorphism.="" =="[" ]="" [="" ]="" (="" )="" p="" p="" definition="" 7.="" if="" m(x)="" is="" a="" monic="" irreducible="" polynomial="" in="" z="" x="" and="" x="" is="" a="" primitive="" (generator)="" of="" z="" x="" m(x)="" then="" m(x)="" is="" called="" a="" primitive="" polynomial.="" remark="" 10="" and="" example="" 4="" revisited:="" not="" every="" ir="" *="" [="" ]="" (="" )="" 4="" 3="" 2="" 4="" 3="" 2="" 2="" x+1="" reducible="" polynomial="" is="" primitive.="" consider="" f="Z" x="" x="" +="" x="" +="" x="" +="" x="" +="" 1="" ;="" then="" x="" +="" x="" +="" x="" +="" x="" +="" 1="" is="" not="" primitive="" since="" x="" is="" not="" a="" generator.="" recall="" that="" x="" +="" 1="" is="" a="" generator="" of="" f="" and="" m="" (y)="" *="" 4="" 3="" 4="" 3="y" +="" y="" +="" 1.="" thus,="" by="" the="" result="" of="" the="" example,="" x="" +="" x="" +="" 1="" is="" primitive.="" [="" ]="" (="" )="" [="" ]="" 4="" 3="" 2="" 4="" 2="" exercise="" 10.="" (submit="" this="" one)="" a)="" prove="" directly="" that="" x="" is="" a="" generator="" of="" z="" x="" x="" +="" x="" +="" 1="" b)="" prove:="" x="" +="" x="" +="" 1="" z="" x="" is="" primitive.="" example="" 4.="" revisited="" again:="" now="" x="" (="" )(="" )(="" )(="" )(="" )="" [="" ]="" 15="" 4="" 3="" 2="" 4="" 3="" 4="" 2="" 15="" 2="" +="" 1="x" +="" x="" +="" x="" +="" x="" +="" 1="" x="" +="" x="" +="" 1="" x="" +="" x="" +="" 1="" x="" +="" x="" +="" 1="" x="" +="" 1="" so,="" of="" the="" three="" irreducible="" factors="" of="" x="" +="" 1="" in="" z="" x="" of="" degree="" four,="" two="" are="" primitive.="" [="" ]="" k="" p="" p="" remark="" 11.="" motivated="" by="" the="" previous="" example="" we="" shall="" study="" the="" factorization="" of="" x="" x="" over="" z="" x="" next.="" this="" study="" will="" enable="" us="" to="" conclude="" that="" for="" every="" positive="" integer="" k="" a="" monic="" irreducible="" pol="" -="" ynomial="" of="" degree="" k="" in="" z="" x="" .="" in="" p="" [="" ]="" preparation="" for="" this="" result="" we="" obtain="" a="" useful="" number-theoretic="" lemma.="" r="" s="" lemma="" 3.="" if="" n="" 2="" and="" s="" r="" 1,="" then="" n="" 1="" n="=" =="" -="" -="" 1="" if="" and="" only="" if="" r="" s.="" 14="" (="" )="" (="" )="" (="" )="" (="" )="" s="" r="" m-1="" r="" m-2="" r="" r="" r="" s="" r="" s="" proof="" observe="" that="" if="" r="" s="" then="" s="mr" and="" n="" -="" 1="n" 1="" n="" +="" n="" +="" +="" n="" +="" 1="" so="" n="" -="" 1="" n="" -="" 1.="" conversely,="" suppose="" n="" -="" 1="" n="" 1="" and="" write="" s="q" r="" +="" t="" where="" t="">< r.="" th="" -="" ··="" -="" s="" q="" r="" +="" t="" qr="" +="" t="" t="" t="" t="" qr="" t="" r="" qr="" r="" t="" en="" n="" -="" 1="n" 1="n" n="" +="" n="" 1="n" n="" 1="" +="" n="" -="" 1="" now="" by="" the="" first="" part="" of="" the="" argument="" n="" 1="" n="" 1="" and="" so="" n="" 1="" n="" -="" 1="" as="" 0="" -="" -="" -="" -="" -="" -="" -="[" ]="" m="" n="" t="">< r="" we="" see="" that="" t="0." exercise="" 11.="" (submit="" this="" one)="" prove:="" if="" f="" is="" any="" field="" then="" x="" -="" 1="" x="" -="" 1="" in="" f="" x="" if="" and="" only="" if="" m="" n.="" [="" ]="" k="" k="" p="" p="" p="" theorem="" 5.="" let="" p="" be="" prime="" and="" k="" 1.="" then="" (a)="" an="" irreducible="" polynomial="" f(x)="" z="" x="" divides="" x="" x="" if="" and="" only="" if="" deg="" f="" k;="" (b)="" x="" 1="" is="" the="" product="" of="" all="" monic="" irreducible="" polynomials="" fro="?" -="" -="" p="" [="" ]="" m="" z="" x="" having="" degree="" that="" divides="" k.="" 15="" [="" ]="" (="" )="" deg="" f-1="" deg="" f="" p="" p="" proof="" (a)="" consider="" f="Z" x="" f(x)="" where="" f(x)="" x.="" of="" course="" f="p" .="" now="" f(x)="" is="" the="" minimal="" polynomial="" of="" x="" in="" f="" so="" by="" theorem="" 3="" f(x)="" x="" 1="" but="" deg="" f="" k="" implies="" p="" -="" [="" ]="" (="" )="" deg="" f="" k="" k="" k="" deg="" f="" k="" p="" 1="" p="" 1="" p="" 1="" p="" 1="" p="" 1="" p="" -="" 1="" by="" lemma="" 2="" and="" this="" in="" turn="" forces="" x="" -="" 1="" x="" -="" 1="" by="" exercise="" 11.="" hence="" f(x)="" x="" 1.="" conversely,="" suppose="" f(x)="" x="" -="" 1="" and="" again="" consider="" f="Z" x="" f(x)="" .="" -="" -="" -="" -="" -="" -="" (="" )="" k="" k="" d="" 0="" 1="" d="" 0="" 1="" d="" p="" d="" i="" p="" p="" i="" i="0" let="" be="" a="" primitive="" of="" f="" and="" write="a" +="" a="" +="" +="" a="" x="" where="" d="deg" f="" and="" a="" ,="" a="" ,...,="" a="" z="" .="" then,="" by="" lemma="" (3)="" a="" x="" in="" f="" b="" a="" a="" a="" ··="" =="" k="" k="" k="" k="" p="" p="" p="" p="" 1="" d="" k="" ut="" f(x)="" x="" -="" x="" and="" f(x)="0" in="" f="" force="" x="x" in="" f.="" thus="and" =="" 1.="" hence="" ord="p" -="" 1="" p="" -="" 1="" from="" which="" it="" follows="" by="" lemma="" 2="" that="" deg="" f="d" k.="" a="" a="" a="" a="" -="" (="" )="" k="" i="" m="" e="" p="" i="" i="1" proof="" (b)="" we="" know="" from="" theorem="" 3="" of="" module="" v="" that="" x="" x="f" (x)="" -="" 1="" 2="" m="" p="" [="" ]="" 1="" 2="" m="" i="" i="" where="" f="" ,="" f="" ,..,="" f="" are="" distinct="" monic="" irreducible="" polynomials="" from="" z="" x="" and="" e="" ,="" e="" ,..,="" e="" are="" positive="" integers.="" we="" claim="" that="" each="" e="1." indeed,="" suppose="" some="" e="" 2.="" then="(" )="" k="" 2="" p="" i="" x="" -="" x="f" (x)="" n(x)="" [="" ]="" [="" ]="" p="" p="" where="" n(x)="" z="" x="" .="" now="" it="" is="" the="" case="" that="" the="" ordinary="" algebraic="" rules="" of="" differentiation="" of="" polynomials="" hold="" for="" z="" x="" but="" we="" defer="" the="" verification="" of="" these="" rules="" to="" appendix="" i="" (for="" the="" interested="" re="" ader).="" 16="" (="" )="" (="" )="" (="" )="" (="" )="" (="" )="" k="" 2="" k="" p="" 1="" i="" i="" 2="" i="" i="" hence="" p="" 1="" x="" -="" 1="2" f="" (x)="" n(x)="" +="" f="" (x)="" n="" (x)="" or,="" equivalently,="" -="" 1="2" f(x)="" n(x)="" +="" f="" (x)="" n="" (x)="" thus="" f="" (x)="" 1="" (even="" if="" p="2" and/or="" n="" (x)="0)" -="" a="" contradiction.="" therefore="" -="" '="" '="" -="" '="" k="" m="" p="" i="" i="1" x="" x="f" (x)="" -="" k="" i="" m="" p="" i="" i="1" of="" course="" deg="" f="" k="" for="" each="" i="" by="" (a)="" of="" this="" theorem.="" moreover,="" if="" f(x)="" is="" monic="" and="" irreducible="" with="" k="" divisible="" by="" deg="" f="" then="" f(x)="" x="" -="" x="f" (x)="" thus,="" it="" follows="" by="" propo="" [="" ]="" i="" p="" p="" sition="" 4="" of="" module="" v="" that="" f(x)="f" (x)="" for="" some="" 1="" 1="" m="" and="" the="" proof="" is="" complete.="" corollary="" 5.1="" and="" remark="" 12.="" let="" d="" k="" and="" denote="" by="" i="" (d)="" the="" number="" of="" monic="" irreducible="" polynomials="" in="" z="" x="" having="" t="=" k="" p="" d="" k="" p="" he="" degree="" d.="" then="" p="d" i="" (d)="" with="" the="" aid="" of="" "mobius="" inversion",="" to="" be="" presented="" in="" a="" subsequent="" lemma,="" we="" shall="" obtain="" a="" formula="" for="" i="" (k).="" then="" by="" using="" some="" simple="" inequalities="" we="" will="" show="" that="" i="" (k)=""> 0 p primes p and k 1. ? ? = k p p Proof It is enough to note that d I (d) is the contribution of the monic irreducible polynomials having degree d to the degree of x 1. Then the formula follows by b) of Theorem 5. - { } + r 1 2 r 1 r Definition 8. (Mobius Function) The function : Z -1, 0, 1 1 if n = 1 n (n) = (-1) if n = p p p 0 otherwise where p ,..., p a µ µ µ ? ? ? ? ··· ? ? ? re distinct primes, is referred to as the Mobius function. µ 17 1 2 k d n e e e 1 2 k A salient technical property is given next 1 if n = 1 Lemma 4. (d) = 0 otherwise Proof Of course, if n = 1 the result holds. Suppose n 2, so that n = p p p . Then d n if and o µ ? ? ? = ·· ? ( ) 1 2 k 1 r t t t 1 2 k i i i k r d n r=1 pi , pi k r r=1 k nly if d = p p p where 0 t e . Now if any t 2, (d) = 0 so (d) = 1 + ( 1) k = 1 + (-1) r = 1 + (-1) µ µ ·· ·· = = = - ? ? ? ? ? ? ? ? ? ? = 0 by the Bimomial Theorem. + d n Lemma 5. (Mobius Inversion) Consider two real-valued functions f and g defined on Z related by the expression f(n) = g(d) n 1 Then ? ? = d n n g(n) = (d) f n 1 d µ ? ? ? ? ? = ? ? ? d n d n n d d d n d n n d d Proof Consider n (d) f = (d) g(d ) d n n Now d n and d if and only if d n and d so d d n (d) f = g(d ) (d) d But µ µ µ µ ' ' ' ? ? ' ? ? ? ? ' ' ' ? ? ' ? ? ? ? ? ? ? ? ? ? n d d (d) = 0 if d n and d < n="" µ="" '="" '="" '="" 18="" d="" n="" thus="" n="" (d)="" f="g(n)" d="" and="" the="" proof="" is="" complete.="" µ="" [="" ]="" [="" ]="" (="" )="" p="" k="" p="" theorem="" 6.="" primes="" p="" k="" 1="" (="" a="" monic="" irreducible="" polynomial="" of="" degree="" k="" in="" z="" x="" ).="" consequently="" an="" algebraically="" unique="" finite="" field="" of="" order="" p="" ,="" namely="" z="" x="" f(x)="" ,="" where="" f(x)="" is="" a="" monic="" irred="" =="" [="" ]="" k="" p="" ucible="" polynomial="" of="" degree="" k="" from="" z="" x="" .="" we="" use="" the="" notation="" g="" f="" (p="" )="" to="" denote="" this="" field.="" k="" d="" p="" d="" k="" k="" k="" d="" d="" k,="" d="">1 k-1 k k i k i=1 Proof By Corollary 5.1 and Lemma 4 I (k) = (d) p = p + (d) p p 1 p - p > p > 0 p 1 Hence suc µ µ ? ? - = - ? ? ? ? - ? ? ? ? h a polynomial in Z x . p [ ] Remark 13. and Exercise 12. (Submit this one) The Mobius function and Mobius Inversion are important number-theoretic topics with many applications, in addition to the application given here. Consult µ d n k i=1 i Appendix II for two more. Furthermore, the Mobius function and the Euler - function are related as follows: n (n) = (d) . d 1 a) Prove this. Hint: Write (n) = n 1 - , where p ? ? µ ? ? ? ? ? ? ? ? ? 1 2 k e e e 1 2 k d n n = p p p , and expand the product b) Prove (using Mobius inversion): n = (d). ? ·· ? 19 k k k In the remainder of this module we study the structure of GF(p ). Specifically, we determine which finite fields GF(p ) are subfields of GF(p ). Proposition 6. If GF(p ) is a subfield of GF(p )   k k k then k. Proof Consider a primitive GF(p ) . Since GF(p ) as well p - 1 = ord GF(p ) = p 1 Thus k by Lemma 3. The converse requires a little more work. a a a * * * ? ? -     k k k k Proposition 7. If k then GF(p ) is a subfield of GF(p ). Proof Since GF(p ) is cyclic and p 1 p 1 by Lemma 2, GF(p ) has a unique cyclic subgroup of order p - 1, say H. It is enough to prove th * * - -     { } { } { } k i j at H 0 is a subgroup of (GF(p ), +). To do this consider a, b H 0 . Since a - b H 0 trivially if either a or b = 0 suppose a = and b = where is a primitive of H. Now (a - a a a ? ? ? ? ? p p p b) = a - b .    p p p p 1 (Proof: Exercise 13.) and, since a a and b = b by Euler's Theorem and induction it follows that (a - b) = a - b. Thus, if a b (a- b) = 1 and, because H contains ALL - = ?     { } elements having order that divides p 1, a - b H. Of course if a = b a -b = 0 H 0 . - ? ? ?  12 Example 5. We draw a hierarchical diagram of the subfield structure of GF(3 ) indicating subfield inclusions: GF( 12 3 ) GF( 6 3 ) GF( 3 3 ) GF(3) GF( 2 3 ) GF( 4 3 ) 20 100 Exercise 14. (Submit this one) Detrmine the subfields of GF(5 ) and draw a hierarchical diagram indicating subfield inclusions.