Universit a tea Alexandr u Io an Cuza din Ia³i [605843]

Universit a tea Alexandr u Io an Cuza  din Ia³i
F a cul t a tea de Ma tema tic 
Polinoame peste corpuri finite
³i aplica µii
Lucrare de disertaµie
Conduc tor ³tiinµic:
Conf. dr. V olf Aurelian ClaudiuCandidat: [anonimizat] “tef ania-Alina
Iulie, 2019
Ia³i

Cuprins
Prefaµ  2
1 Preliminarii 3
1.0.1 Inel. Corp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.0.2 Extinderi de corpuri . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Corpuri nite 7
3 Algoritmi de factorizare în Fp[X] 15
4 P olinoame ireductibile p este Fq[X] 20
Bibliograe 24
1

Prefaµ 
2

Capitolul 1
Preliminarii
1.0.1 Inel. Corp
În cele ce urmeaz , v om en unµa noµiuni de baz  ³i rezultate f r  demonstraµii din teoria
extinderilor de corpuri.
Deniµie 1.1. Se nume³te inel, ³i se note az  (R;+;
) , o mulµime R6= 0 înzestr at  cu
dou  le gi de c omp oziµie, ;;+" ³i;;
" , astfel înc ât sunt satisf cute urm to ar ele axiome:
i)(R;+) grup ab elian,
ii)(R;
) semigrup,
iii);;
" este distributiv  faµ  de ;;+" .
Dac  ,8a;b2R ,a
b=b
a , atunci spunem c   R este inel c omutativ.
Dac   exist  12R astfel înc ât 1
a=a
1 =a ,8a2R , atunci spunem c   R este inel
unitar.
Un inel c omutativ, unitar ³i f r   divizori nenuli ai lui zer o se nume³te inel inte gru.
Deniµie 1.2. Fie1 elementul unitate al inelului R ³in2N . Not m cu n
1 multiplul
1 + 1 +:::+ 1 (n termeni).
Denim c ar acteristic a lui R, notat  c ar R , în felul urm tor:
 dac   p entru oric e n2N,n
1 = 0 , atunci avem
carR = 0;
 dac   exist  n2Nastfel înc ât n
1 , atunci
carR =minfn2Njn
1 = 0g:
Deniµie 1.3. Un domeniu de inte gritate R se nume³te inel euclidian dac   exist  o
funcµie:R!N astfel înc ât;
(1)(a) = 0()a= 0;
(2)(ab) =(a)(b) , oric ar e ar  a;b2R;
(3) Oric ar e ar  a;b2R;b6= 0 , exist q;r2R astfel înc ât
a=bq+r;(r)<(b):
3

4
Proprietatea (3) din deniµie este cunoscut  sub n umele de teorema împ rµirii cu
rest inR ",q este n umit c ât , iarr r est al împ rµirii lui a prinb .
FieR un domeniu de in tegritate ³i a;b2R . Un elemen t d2R se n ume³te c el mai
mar e divizor c omun (p e scurt cmmdc ) al luia ³ib dac  sun t satisf cute condiµiile:
i)dja ³idjb ;
ii) dac cja ³icjb , atuncicjd
Dac  1 este cmmdc al elemen telor a ³ib , spunem c  a ³ib sun t prime într e ele (sau
r elativ prime ).
T eorem  1.4. (A lgoritmul lui Euclid). Fie R un inel euclidian ³i a;b2R; cub6= 0 .
A tunci exist  un cmmdc d al elementelor a ³ib ;d se p o ate aa prin urm torul algoritm:
Algoritm Euclid (a;b;d )
Se dau :a;b2R:
Se obµine :d= (a;b)2R .
Încep e
Dac b= 0 , atuncid=a; Stop .
P as 1 . G se³teq;r2R cua=bq+r ³ir= 0 sau(r)<(b):
Dac r= 0 , atuncid=b ; Stop .
(Dac r6= 0" ) Punea b ,b r . Mergi la P as 1 .
Sfâr³it
În plus, exist  (³i se p ot determina algoritmic) u;v2R astfel înc ât d=au+bv .
Deniµie 1.5. Se nume³te c orp un inel unitar (K;+;
) în c ar e oric e element nenul ar e
un invers faµ  de înmulµir e.
Un c orp în c ar e înmulµir e a este c omutativ  se nume³te c orp c omutativ.
În con tin uare, toate corpurile considerate v or  com utativ e.
Deniµie 1.6. FieK un c orp ³iLK o submulµime a sa. A tunci L este un sub c orp
înK dac   sunt satisf cute urm to ar ele c ondiµii:
i)xy2L ,8x;y2L;
ii)x
y12L ,8x;y2L ,y6= 0 .
Prop oziµie 1.7. (lema chinez  a r esturilor) Fie K un c orp c omutativ ³i m1(X);:::;mr(X)2
K[X] astfel înc ât (mi(X);mj(X)) = 1 oric ar e ar  i6=j . Dac  m(X) =m1(X)m2(X):::mr(X) ,
atunci oric ar e ar  p olino amele g1(X);:::gr(X)2K[X] , exist  un unic p olinom g(X)2
K[X] astfel înc ât
g(X)gi(X)( mo dmi(X));1ir
³i gr adg(X)< gr adm(X) (p entruf;g;h2K[X] scriemfg( mo dh),h dividefg ).
1.0.2 Extinderi de corpuri
Deniµie 1.8. FieK un c orp c omutativ ³i L un sub c orp al s u. Corpul K se nume³te
extinder e a lui L ³i not mK=L sauLK .
4

5
Deniµie 1.9. FieF un sub c orp al lui E . Spunem c   FE este o extinder e nit , dac  
sp aµiul liniar FE ar e dimensiune nit , adic   dimFE <1 . Not mdimFE cu[E:F] .
(Dimensiune a ac estui sp aµiu liniar se mai nume³te gr adul extinderii.)
Deniµie 1.10. Numim sub extinder e a extinderii KL oric e sub c orp E al luiL c ar e
includeK . Sub extinder e a E se nume³te sub extinder e pr oprie dac   E6=K ³iE6=L .
T eorem  1.11. (T r anzitivitate a extinderilor nite)
a) FieKL ³iLM extinderi nite de c orpuri. A tunci extinder e a KM este nit 
³i ar e lo c e galitate a:
[M:K] = [M:L]
[L:K]
(gr adul este multiplic ativ).
Mai pr e cis, dac  fx1;:::;xmg este oK -b az  a luiL , iarfy1;:::;yng este oL -b az  a lui
M , atuncifx1y1;:::;x 1yn;:::xmy1;:::xmyng este oK -b az  a luiM .
b) Dac  KM este o extinder e nit  de c orpuri, iar L este o sub extinder e a sa, atunci
KL ³iLM sunt nite.
Deniµie 1.12. FieFE ³ia2E . Spunem c   a este element algebric p este F ³i
not ma alg=F , dac   exist  un p olinom nenul f2F[X] astfel înc ât f(a) = 0 .
Deniµie 1.13. O extinder e de c orpuri KL se nume³te extinder e algebric   dac  
oric ar e ar  a2L ,a este algebric p este K .
Deniµie 1.14. FieK ³iK0dou  c orpuri. Se nume³te morsm de c orpuri de la K la
K0oric e funcµie f:K!K0c e satisfac e c ondiµiile:
i)f(a+b) =f(a) +f(b) ,8a;b2K ;
ii)f(a
b) =f(a)
f(b) ,8a;b2K;
iii)f(1K) = 1K0 .
Dac  , în plus, f este bije ctiv , atunci f se nume³te izomorsm de c orpuri.
Deniµie 1.15. FieKL . Un K-automorsm al lui L este un morsm bije ctiv de
c orpuri,:L!L cu=K=id . (În ac est c az, 1este totK -automorsm al lui L .)
Deniµie 1.16. FieKL o extinder e de c orpuri. A tunci mulµime a elementelor din
L algebric e p este K se note az  cu K0
L ³i se nume³te închider e a algebric   a lui K înL .
Evident,KK0
L .
Deniµie 1.17. Se nume³te c orp algebric închis un c orp c ar e satisfac e urm to ar ele pr o-
priet µi e chivalente:
a) Nu exist  extinderi algebric e pr oprii ale lui K .
b) Nu exist  extinderi nite pr oprii ale lui K .
c) Pentru oric e extinder e KL , închider e a algebric   a lui K înL c oincide cu K . (Se
mai spune  K este algebric închis în L .)
d) Oric e p olinom cu c o ecienµi în K , de gr ad c el puµin 1 , ar e o r  d cin  în K .
e) Oric e p olinom cu c o ecienµi în K , de gr adn1 , ar en r  d cini în K .
f ) Singur ele p olino ame ir e ductibile din K[X] sunt c ele de gr ad 1 .
5

6
T eorem  1.18. FieK un c orp. A tunci exist  o extinder e algebric   c ar e este c orp algebric
închis. Un astfel de c orp se nume³te închider e algebric   a lui K .
T eorem  1.19. FieK un c orp. A tunci oric ar e dou  închideri algebric e ale lui K sunt
K -izomorfe.
Deniµie 1.20. FieFK ³ia alg=F ,a2K . Polinomul minimal al lui a p esteF ,
notatIrr(a;F) sauma , este p olinomul ir e ductibil în F[X] , cu c o ecientul dominant e gal
cu1 ³i c ar e ar e p e a c a r  d cin .
Deniµie 1.21. FieR un inel inte gru, f2R[X] un p olinom nenul, a2R o r  d cin  a
luif ³ir2N . Spunem c   a este r  d cin  multipl  de or din r a luif dac  
(Xa)rjf ³i(Xa)r+1-f:
Num rul natur al r se nume³te or dinul de multiplicitate al r  d cinii a .
Deniµie 1.22. FieR un inel c omutativ unitar ³i f=a0+a1X+:::+anXn2R[X] .
Numim derivat  formal  a p olinomului f p olinomul
df:=a1+ 2a2X+:::+nanXn1:
Se mai folose³te notaµia df=f0saudf=f(1).
Un calcul direct arat  c  deriv ata formal  are propriet µile uzuale ale deriv atei cu-
noscute din Analiz :
(f+g)0=f0+g0;8f;g2R[X];
(af)0=af0;8a2R;8f2R[X]
(fg)0=f0g+fg0;8f;g2R[X]:
Prop oziµie 1.23. FieR un inel inte gru, f2R[X] un p olinom de gr ad n>0 ³ia2R .
a) Exist  ³i sunt unic e elementele b0;b1;:::;bn2R astfel înc ât f=P
0inbi(Xa)i:
b) Dac  a este r  d cin  multipl  de or din m ( m2N) a p olinommului f , atuncif(i)(a) =
0 , p entru oric e i2f0;:::;m1g .
c) Dac  f(a) =f0(a) = 0 , atuncia este r  d cin  multipl  a lui f (de multiplicitate c el
puµin 2).
Prop oziµie 1.24. FieK un c orp ³if2K[X] . A tuncif ar e r  d cini multiple dac   ³i
numai dac  
cmmdc (f;f0)6= 1:
6

Capitolul 2
Corpuri nite
Deniµie 2.1. FieK un inel c omutativ, carK =p>0: Consider  m aplic aµia:
':K!K;'(x) =xp;8x2K:
A v em c '(xy) = (xy)p=xpyp='(x)'(y);8x;y2K ³i
'(x+y) = (x+y)p=X
0ipCi
pxpiyi=xp+yp;
cum co ecienµii binomiali Ci
p sun t divizibili prin p p en tru 1ip1 , atunci este
adev  rat  ³i ultima egalitate.
Astfel,' este morsm de inele , n umit endomorsmul lui F r ob enius al luiK . Imaginea
lui' esteKp:=fxpjx2Kg , care este subinel în K . În cazul inelelor de caracteristic 
0, denim endomorsm ul lui F rob enius ca ind aplicaµia iden tic , '=id:K!K . Ne
v om a juta de aceste rezultate mai ales în cazul K corp (dar ³i p en tru inele, de exemplu
inelulK[X] , cuK corp de caracteristic  p ). Endomorsm ul lui F rob enius este aplicaµia
iden tic  în cazul corpului Fp .
T eorem  2.2. FieF un c orp nit cu q elemente. A tunci c ar F este un num r prim p ³i
exist n2Nastfel înc âtjFj=pn.
Demonstr aµie. Fiee elemen tul unitate al lui F . A tunci m ulµimea m ultiplilor lui e ,
P:=fn
ejn2Ng , este o subm ulµime a lui F ³i este nit . Deci exist  p2Nastfel
încâtp
e= 0 . Alegemp s  e minim cu aceast  proprietate ( p= carF ). Dac p n u ar 
prim, atunci p=ab , cu1<a ,b<p . Cump
e= (ab)
e= (a
e)(b
e) = 0 , rezult  c 
a
e= 0 saub
e= 0 , con tradicµie cu minimalitatea lui p .
R mâne c  exist  un unic p prim astfel încât p
e= 0 . A³adarP=f0; e;2e;:::;
(p1)eg . Observ  m c  exist  o bijecµie în tre P ³iZp=fb0;b1;:::;[p1g , dat  dei
e7!bi .
Este c hiar un izomorsm, dup  cum se v eric  u³or. Deci P este corp (ind izomorf cu
corpul Zp ), iarF este o extindere a sa.
In terpret m F ca un spaµiu liniar p este P . A tunci dimensiunea lui F p esteP este
nit , e dim pF=n . DeciF=Pn(izomorsm de spaµii liniare), adic  jFj=pn.
7

8
T eorem  2.3. Fie p un num r prim ³i
o închider e algebric   a c orpului Fp .
a) Fien2N³iq=pn. Exist  un unic sub c orp F al lui
cu q elemente, anume
c orpul de desc ompuner e a p olinomului XqX p esteFp . În p articular, exist  un c orp
nit cupnelemente ³i oric e dou  c orpuri cu pnelemente sunt izomorfe.
b) Dac  F este un c orp cu pnelemente, iar K este un sub c orp al s u, atunci jKj=
pm, undemjn . R e cipr o c, p entru oric e divizor m al lui n exist  un unic sub c orp al lui F
cupm=:r elemente, ³i anume K=fx2Fjxr=xg:
Demonstr aµie. a) Presupunem c  F
este un corp cu q elemen te. Grupul (F;
) are
q1 elemen te. Aplicând teorema lui Lagrange, a v em c  xq1= 1 , decixq=x ,8x2F.
Sub corpul prim al lui F esteFp . Prin urmare, orice elemen t al lui F este r d cin  a
p olinom ului XqX , considerat cu co ecienµi în Fp . A cest p olinom p oate a v ea cel m ult
q r d cini distincte în
; cumjFj=q , rezult  c  elemen tele lui F sun t r d cinile lui
XqX , adic F este corpul de descompunere p este Fp al luiXqX . Astfel,F este
unicul sub corp cu q elemen te al lui
.
Recipro c, e g=XqX . Mulµimea F a r d cinilor din
ale luig ,F=fx2
j
xq=xg , este sub corp al lui
. În tr-adev  r, aplicaµia :
!
, (x) =xq,8×2
,
este morsm de corpuri (este o putere a endomorsm ului lui F rob enius); m ulµimea F
este atunci sub corpul xat de acest morsm. P e de alt  parte, g are toate r d cinile în

³i n u are r d cini m ultiple, deoarece deriv ata sa este qXq11 =1 , deci n um rul
r d cinilor din
ale luig esteq . De aici concluzion m c  F , corpul de descompunere al
luig p esteFp , areq elemen te.
b) FieK un sub corp al lui F (consider m F
). Notânds:=jKj ³it:= [F:K] ,
a v em c pn=jFj=st; cump este prim, acest fapt este p osibil doar dac  s este de forma
pm³ipmt=pn, adic mjn .
Recipro c, dac  m este un divizor al lui n ,n=mt ³ir:=pm, e :
!
,
(x) =xr,8×2
. Not m cu L=fx2
jxr=xg=fx2
j (x) =xg . Am v  zut c 
L este sub corp cu r elemen te al lui
. Ar t m c  LF . A v em (  )(x) = (xr) =xr2
³i, prin inducµie, t(x) =xrt,8×2
. Decix2L) (x) =x) t(x) =x)xrt=x .
Darrt=pn, iarF=fx2
jxpn=xg ; astfel,x2L)x2F .
Orice sub corp E al luiF cur elemen te coincide cu L p en tru c  orice elemen t din E
satisface ecuaµia xr=x .
Corpul nit cu pnelemen te (unic pân  la izomorsm) se noteaz  cu GF(pn) sauFpn .
NotaµiaGF(pn) pro vine din sin tagma Galois Field (corp Galois).
Prop oziµie 2.4. Pentru oric e n2N, exist  m c ar un p olinom ir e ductibil de gr ad n în
Fp[X] ; p entru oric e astfel de p olinom f ,Fp[X]=(f) este un c orp cu pnelemente.
Demonstr aµie. FieF corpul de descompunere a lui g=XqX p esteFp , undeq=pn.
Lema urm toare asigur  c  (F;
) este grup ciclic. Fie  un generator al lui F³i
f=Irr(;Fp) . A v em c  F=Fp() ³i gradf= [Fp() :Fp] = [F:Fp] =n . A³adar
f este ireductibil de grad n dinFp[X] . A v em ³i Fp[X]=(f)=Fp() , care este corp cu q
elemen te.
8

9
Lem  2.5. Dac  R este inel c omutativ inte gru, iar G este o mulµime nit  de elemente
nenule dinR , atunciG este ciclic. În p articular, oric e sub grup nit al grupului multipli-
c ativKal elementelor nenule ale unui c orp c omutativ K este ciclic.
Demonstr aµie. Se p oate face ap el la teorema factorilor in v arianµi, aplicat  grupului ab e-
lian nitG : dac G n u este ciclic, atunci G=C1:::Cm , undem>2 ,C1;:::;Cm
sun t ciclice,jC1j=d1 ,::: ,jCmj=dm ³id1jd2j:::jdm . A tunci p olinom ul Xdm1
aren r d cini în R , iarn=d1
:::
dm>dm , con tradicµie.
Deci, p en tru orice corp nit F ,(F;
) este grup ciclic. Orice generator al acestui
grup se n ume³te element primitiv al lui F .
Am determinat corpurile nite în ip oteza c  sun t com utativ e. Este remarcabil faptul
c  ip oteza aceasta este în plus: orice corp finit este comutativ . P en tru a demonstra
acest rezultat, facem o cercetare în domeniul r  d cinilor de ordin n ale unit µii ³i al
corpurilor ciclotomice .
Deniµie 2.6. FieK un c orp ³in un num r natur al strict p ozitiv. Elementul 2K se
nume³te r  d cin  a unit µii de or din n din K dac  n= 1 . Not m cu Un(K) (sau, mai
simplu, cu Un , dac   nu exist  p eric ol de c onfuzie) mulµime a r  d cinilor de or din n ale
unit µii din K :
Un:=fx2Kjxn= 1g:
Cum p olinom ul Xn1 are cel m ult n r d cini,Un este subgrup cu cel m ult n elemen te
al grupului (K;
) . Elemen tul 2Un se n ume³te r  d cin  primitiv  de or din n a unit µii
dac  ordin ul lui  în grupulUn esten . (ec hiv alen t, n= 1 , darm6= 1 ,8m<n ). V om
nota cuPn(K) (sau, mai simplu, cu Pn ) m ulµimea r d cinilor primitiv e de ordin n ale
unit µii din K :
Pn(K) :=fx2Un(K)jord x =ng:
Dac  este o r d cin  a unit µii din tr-o extindere a lui K , extinderea KK() se
n ume³te extinder e ciclotomic   .
Observ aµie 2.7. A m v zut c   Un(K) este ciclic (este sub grup nit al lui K). De ci,
exist  o r  d cin  primitiv  de or din n a unit µii în K dac   ³i numai dac   Un(K) ar en
elemente.
Exemple 2.8. a)Un(Q) =f1;1g dac  n este p ar ³iUn(Q) =f1g dac  n este imp ar.
b)Un(C) =fe2ki=njk2f1;:::;ngg; undee2ki=n=cos(2k=n ) +isin(2k=n ) .
Exist '(n) r  d cini c omplexe primitive de or din n ale unit µii; ele sunt de forma e2ki=n
cu(k; n) = 1;1kn: A m notat cu '(n) num rul numer elor mai mici c a n , prime
cun ; funcµia':N!Ndenit  astfel se nume³te funcµia indic ator a lui Euler.
c)U4(F5) =F
5=f1;2;3;4g (din te or ema lui L agr ange); P4(F5) =f2;3g ;U4(F7) =
f1;6g ;P4(F7) =? .
Prop oziµie 2.9. FieK un c orp,
o închider e algebric   a sa ³i n2N.
a)Un(
) ar en elemente dac   ³i numai dac   c ar K nu divide n.
b) Dac   c ar K=p>0 ³in=ptm , cu(p;m) = 1 , atunciUn(K) =Um(K):
9

10
Demonstr aµie. a) Un(
) aren elemen te dac  ³i n umai dac  p olinom ul f=Xn1 n u are
r d cini m ultiple. Deoarece f0=nXn1, a v em (f0;f) = 1 dac  ³i n umai dac  f06= 0 ,
adic  carK n u dividen .
b) Este clar c , în general, mjn implic UmUn . Fiept:=q . Dac x2Un ,
xn= (xm)q= 1 . Dar aplicaµia y7!yq;8y2K , este morsm (injectiv) de corpuri (este
o putere a endomorsm ului F rob enius), a³adar yq= 1 implic y= 1 . Astfel,x2Un
implic xm= 1 , adic x2Um .
Astfel, este sucien t s  se studieze Un(K) în cazul în care car K n u dividen . În acest
caz exist  o r d cin  primitiv   de ordin n în tr-o extindere a lui K .
Deniµie 2.10. Fien2N³i K un c orp c ar e c onµine o r  d cin  primitiv  de or din n a
unit µii. Polinomul (din K[X] )
n:=Y
2Pn(K)(X)
se nume³te al n-le a p olinom ciclotomic p este K . R  d cinile lui n sunt distincte ³i sunt
r  d cinile primitive de or din ale unit µii din K; gr ad n='(n) . Dac   c ar K= 0 (de
obic ei se ia K=C ), numim
n:=Y
k<n; (k;n)=1(Xe2ki=n)
al n-le a p olinom ciclotomic (f r   menµionar e a c orpului K ).
Prop oziµie 2.11. Fien2N³i K un c orp c ar e c onµine o r  d cin  primitiv  de or din n
a unit µii. A tunci:
a) Pentru oric e divizor natur al d al lui n, exist  o r  d cin  primitiv  de or din d a
unit µii în K.
b) A r e lo c e galitate a Xn1 =Q
djnd .
c) Co ecienµii lui n se g sesc în sub c orpul prim P al luiK .
d) Dac   c ar K= 0 (de exemplu K=C ), atunci n2Z[X] .
Demonstr aµie. a) Dac  este o r d cin  primitiv   de ordin n a unit µii ³i m=n=d ,
atuncimeste o r d cin  primitiv   de ordin d a unit µii.
b) P olinoamele din am bii mem bri ai egalit µii sun t unitare ³i au acelea³i r d cini,
an ume r d cinile de ordin n ale unit µii din K .
c) Demonstr m prin inducµie dup  m (1mn ) armaµia: 8d cu1dm ³i
djn , rezult  d2P[X]" .
P en trum= 1 ,1=X12P[X] . Fie 1< mn . Presupunem armaµia
adev  rat  p en tru orice q<m ³i o demonstr m p en tru m . Dac m-n , n u a v em nimic de
demonstrat. Dac  mjn , atunciXm1 = m
g , unde
g=Y
djm;d<md2P[X];
10

11
din ip oteza inductiv  . Din teorema împ rµirii cu rest (a lui Xm1 lag ) înP[X] rezult 
c m2P[X] .
d) Demonstr m prin inducµie dup  m (1mn ) armaµia: 8d cu1dm ³i
djn , rezult  d2Z[X]" .
P en trum= 1 ,1=X12Z[X] . Fie 1< mn . Presupunem armaµia
adev  rat  p en tru orice q<m ³i o demonstr m p en tru m . Dac m-n , n u a v em nimic de
demonstrat. Dac  mjn , atunciXm1 = m
g , unde
g=Y
djm;d<md2Z[X];
din ip oteza inductiv  . Din teorema împ rµirii în tregi (a lui Xm1 lag ) înZ[X] rezult 
c m2Z[X] .
Punctul b) al prop oziµiei furnizeaz  o meto d  recursiv   de calcul al lui n (necesitând
cunoa³terea tuturor d , p en trudjn ,d<n ).
Exemplu 2.12. Consider  m al 7-le a p olinom ciclotomic 7 p este o închider e algebric   a
c orpului cu dou  elemente F2 . Din r elaµia 17 =X71 r ezult  c   7=X6+X5+:::+1 .
Prin înc er c  ri obµinem
7= (X3+X2+ 1)(X3+X+ 1)
unde factorii din dr e apta sunt ir e ductibili în F2[X] (au gr ad 3 ³i nu au r  d cini în F2 ).
A³adar 7 nu este ir e ductibil în F2[X] . Dac   este o r  d cin  primitiv  de or din 7
a unit µii, atunci Irr(;F2) =X3+X2+ 1 sauX3+X+ 1 . A djuncµionând la F2 p e
 se obµine c orpul cu 8 elemente F8 ; oric e element diferit de 1 al lui F
8 este o r  d cin 
primitiv  de or din 7 a unit µii.
Este remarcabil faptul c  în caracteristic  0 fenomen ul descris de exemplul de mai
sus n u apare: p olinoamele ciclotomice p este C sun t ireductibile (în Z[X] ³i înQ[X] ):
T eorem  2.13. Fien2N. A tunci n este ir e ductibil în Z[X] ³i este de ci p olinomul
minimal p este Q al oric  r ei r  d cini c omplexe primitive de or din n a unit µii.
Demonstr aµie. Fie o r d cin  primitiv   complex  de ordin n a unit µii ³i f=Irr(;Q) .
Este sucien t s  ar t m c  f= n ; mai precis, v om ar ta c  f ³in au acelea³i r d cini.
În prim ul rând demonstr m c  f2Z[X] . A ceasta v a  consecinµa un ui fapt mai
general:
Dac  p olinom ul unitar f2Q[X] divide (în Q[X] ) un p olinom unitar u2Z[X] , atunci
f2Z[X] ³iu=fg , cug2Z[X] , unitar. (*)
Din ip otez , exist  g2Q[X] astfel încât fg=u . Fiea (resp ectivb ) cmmmc al
n umitorilor lui f (resp ectiv g). A tunci af;bg2Z[X] ³iaf
bg=abu . T recând la
conµin utul p olinoamelor, obµinem c(af)
c(bg) =ab , deoarecec(u) = 1 . Deciaf=c(af)

f1=c(bg)
g1 , cuf1;g12Z[X] . Se obµine c  c(af)
f1
c(bg)
g1=abu . Simplicând prin
11

12
ab=c(af)
c(bg) , rezult  c  f1g1=u ; cumu este unitar, iar f1;g12Z[X] , concluzion m
c f1;g1 au co ecienµii dominanµi 1 sau -1. Deci f este aso ciat în divizibilitate cu f1 ,
adic f=f12Z[X] . La felg2Z[X] .
Rev enim la demonstraµia teoremei. Orice r d cin  primitiv   de ordin n a unit µii
este r d cin  a lui f . În tr-adev  r, dac   este r d cin  a lui f , atunci corpurile K() ³i
K() sun tK -izomorfe prin tr-un izomorsm care duce p e  în . În particular, rezult 
c ,8m2N;m= 1 dac  ³i n umai dac  m= 1 , adic  ord  =ord .
P ân  aici am demonstrat c  orice r d cin  a lui f este ³i r d cin  a lui n . R mâne
s  demonstr m c  orice r d cin  primitiv   de ordin n a unit µii este r d cin  a lui f .
V om ar ta c , dac  f() = 0 , atuncif(p) = 0 , p en tru orice p prim care n u divide
n . Cumf() = 0 , un raµionamen t inductiv bazat p e aceast  proprietate a lui f arat 
c f(m) = 0 , oricare ar  m prim cun . Astfel, orice r d cin  primitiv   de ordin n a
unit µii v a  r d cin  a lui f .
Fie deci2Pn ³ip prim,p-n . Din (*) rezult  c  n=fg cug2Z[X] , unitar.
Cump2Pn ,f(p)g(p) = n(p) = 0 . Presupunem prin absurd c  f(p)6= 0 , deci
peste r d cin  a lui g. Astfel,  este r d cin  p en tru g1:=g(Xp)2Z[X] . Deoarece
f=Irr(;Q) ,fjg1 înZ[X] (am aplicat (*)), deci g1=fh , cuh2Z[X] , unitar. În
con tin uare, p en tru un p olinom oarecare q2Z[X] , not m cu (q) redusul s u mo dulo
p (p olinom ul din Zp[X] ai c rui co ecienµi sun t imaginile în Zp ale co ecienµilor lui q ;
altfel spus, am notat cu :Z[X]!Zp[X] unica prelungire la Z[X] a morsm ului canonic
Z!Zp ).
Fieg=a0+a1X+:::+Xn. A tunci(gp) =(g)p= ((a0)+(a1)X+:::+Xn)p=
(a0)p+(a1)pXp+:::+Xpn=(a0) +(a1)Xp+:::+Xpn=(g1) . Cumg1=fh ,
obµinem c  (g1) =(g)p=(f)(h) . Deci(f)j(g)pînZp[X] , adic  toµi factorii
ireductibili ai lui (f) se g sesc prin tre cei ai lui (g) . Cum grad (f) =gradf , exist  un
factor ireductibil com un h al lui(f) ³i(g) , de grad1 . Dar atunci (n) =(f)(g)
este divizibil cu h2, adic  are r d cini m ultiple. A ceasta este absurd, c ci njXn1 ,
deci(n)j(Xn1) , care n u are r d cini m ultiple: deriv ata sa este nXn16= 0 în
Zp[X] (p-n implic n in v ersabil în Zp ) ³i(Xn1) este prim cu nXn1.
Prop oziµie 2.14. Fie G un grup ³i a2G .
a) Mulµime a C(G) :=fx2Gjxy=yx;8y2Gg (numit  c entrul lui G) este un
sub grup normal ab elian al lui G.
b) Mulµime a C(a) :=fx2Gjxa=axg (numit  c entr alizatorul lui a în G) este un
sub grup al lui G.
c) R elaµia  de c onjugar e" în G, denit  prin: 8x;y2G;xy dac   ³i numai dac  
9z2G astfel înc ât y=z1xz , este o r elaµie de e chivalenµ  p e G. Dac   xy , spunem
c   x este c onjugat cu y.
d) Dac   not m Ca:=fx2Gjxag (numit  clasa de c onjugar e a elementului a),
atuncijCaj= [G:C(a)] (indic ele sub grupului C(a) în G).
12

13
e) (formula claselor de c onjugar e ) A r e lo c r elaµia:
jGj=jC(G)j+X
a2S[G:C(a)];
unde suma se fac e dup   un sistem S de r epr ezentanµi ai claselor de c onjugar e ale elemen-
telor c ar e nu ap arµin c entrului grupului G.
Demonstr aµie. a) P en tru orice x2G ,z2C(G) a v emx1zx=x1xz=z2C(G) ,
adic C(G) este subgrup normal al lui G . Com utativitatea este eviden t .
b) Fiey;z2C(a) , atunciya=ay ³iza=az . Deducem imediat c  y1a=ay1
iar(y1z)a=y1(za) =y1(az) = (y1a)z= (ay1)z=a(y1z) . Am obµin ut astfel c 
y1z2C(a); deciC(a)G:
c) P en tru orice x2G a v emx= 11×1)xx , adic  relaµia este reexiv  .
Dac x;y2G ³ixy , atunci9z2G astfel încât y=z1xz . Cumx=zyz1=
(z1)1yz1)yx , adic  relaµia este ³i simetric .
Fie acumx;y;t astfel încât xy ³iyt . A tunci9z;w2G astfel încât y=z1xz
³it=w1yw . Deducem c  t=w1(z1xz)w= (w1z1)xzw = (zw)1x(zw) , rezult 
c xt , adic  relaµia este ³i tranzitiv  , deci este relaµie de ec hiv alenµa p e G .
d) Este clar c  Ca=fz1azjz2Gg . FieG=C(a) :=fC(a)xjx2Gg m ulµimea
claselor la dreapta ale subgrupului C(a) înG . Denim aplicaµia ':G=C(a)!Ca ,
prin'(C(a)x) =x1ax ,8x2G . Aplicaµia ' este corect denit  (n u depinde de repre-
zen tan tul ales p en tru clasa la dreapta C(a)x ). În tr-adev  r,8x;y2G , a v emC(a)x=
C(a)y,xy12C(a) . Darx1ax=y1ay,axy1=xy1a,xy12C(a) . Deci,
dac x ³iy au aceea³i clas  la dreapta mo dulo C(a) , atuncix1ax=y1ay . Rezult  ³i
injectivitatea lui ' , c cix1ax=y1ay implic C(a)x=C(a)y . Cum surjectivitatea
lui' este eviden t , obµinem c  jCaj=jG=C(a)j= [G:C(a)] .
e) Din c) rezult  c G este reuniunea disjunct  a claselor de ec hiv alenµ  în rap ort cu
relaµia de conjugare. Se v ede imediat c  a2C(G),Ca=fag,jCaj= 1 . FieS un
sistem de reprezen tanµi ca în en unµ. A tunci S[C(G) este un sistem de reprezen tanµi
p en tru clasele de conjugare, deci G=[fCaja2S[C(G)g= ([fCaja2Sg)[C(G) .
Reuniunile sun t disjuncte, deci, trecând la cardinali ³i µinând con t de punctul d) , obµinem
relaµia dorit .
T eorem  2.15. (W e dderburn, 1909) Oric e c orp nit este c omutativ.
Demonstr aµie. FieK un corp nit. Caracteristica p a luiK este în mo d necesar p ozitiv  .
FieC cen trul corpului K , adic C:=fx2Kjxy=yx;8y2Kg . Se v eric  u³or c  C
este sub corp al lui K , com utativ, de caracteristic  p .
A v em deci extinderile ZpCK . Notândm= [C:Zp] ³in= [K:C] , rezult 
jCj=pm:=q ³ijKj=qn. Este sucien t s  ar t m c  n= 1 .
Presupunem prin absurd c  n > 1 . Cen trul grupului (K;
) esteC. P en tru orice
a2K e m ulµimeafx2Kjxa=axg=:Z(a) , despre care se v ede imediat c  este
subgrup în K ³i include p e C . Cen tralizatorul lui a2Keste c hiarZ(a):=Z(a)nf0g .
13

14
Fied(a) = [Z(a) :C] , decijZ(a)j=qd(a). Cum m ultiplicativitatea gradelor este
v alabil  ³i p en tru extinderi de corpuri n u neap rat com utativ e, din ³irul de extinderi
ZpCZ(a)K rezult d(a)jn . În grupul Kaplic m form ula claselor de
conjugare:
jKj=jCj+X
a2S[K:Z(a)];
unde am notat cu S un sistem de reprezen tanµi ai claselor de conjugare al elemen telor
care n u aparµin lui C. Observ  m c  a2S implic d(a)6=n (altfel ar rezulta Z(a) =K ,
adic a2C, con tradicµie). Înlo cuind cu n um rul de elemen te al ec rui subgrup care
apare, obµinem
qn1 =q1 +X
a2Sqn1
qd(a)1: (2.1)
P olinom ul ciclotomic (p este C )n divide p e (Xn1)=(Xd(a)1) înZ[X] ,8a2S .
În tr-adev  r din 2.11 b) a v emXn1 = n
Q
djn;d6=nd ; cumd(a)jn ,d(a)6=n ³i
Xd(a)1 =Q
djd(a)d , obµinem armaµia.
Deci n(q) divide p eqn1 ³i p e (qn1)=(qd(a)1) ,8a2S ; din egalitatea 2.1 rezult 
c n(q)j(q1) .
P e de alt  parte, jn(q)j=Q
2Pnjqj . Are lo cjqj>q1;8n2;82Pn .
Decijn(q)j>q1 , con tradicµie cu n(q)jq1 .
14

Capitolul 3
Algoritmi de factorizare în Fp[X]
P en tru p olinoamele din Fp[X] ,p n um r prim, exist  un algoritm de descompunere des-
cop erit în an ul 1967 de Berlek amp. În cele ce urmeaz  v om prezen ta acest algoritm.
Lem  3.1. Fief2Fp[X] ,f monic ³i gr ad f=n > 1 . Exist  un p olinom monic
'(X)2Fp[X] astfel înc ât f(X)j'(X)p'(X) ³i1grad' (X)< n dac   ³i numai
dac  f admite c el puµin doi divizori monici ir e ductibili distincµi din Fp[X] .
Demonstr aµie. Cumip=i , oricare ar  i2Fp , rezult  c  p olinom ul
XpX2Fp[X]
are în Fp r d cinile 0;1;2;:::;p1 , deci
XpX=X(X1)(X2):::(X(p1))
de unde
'(X)p'(X) ='(X)('(X)1)('(X)2):::('(X)(p1)) (3.1)
oricare ar  '(X)2Fp[X] .
Presupunem c  f(X) admite cel puµin doi divizori monici ireductibili. Putem scrie
f(X) =1(X)e1:::r(X)er; r> 1; ei1
p en tru 1ir , unde1(X);:::;r(X) sun t p olinoame monice ireductibile distincte
dinFp[X] . Fiec1;:::;cr2Fp , n u toµi egali. Conform lemei c hineze a resturilor, exist 
'(X)2Fp[X] astfel încât grad '(X)<n ³i
'(X)ck(mod ek
k);1kr:
A v em grad '(X)1 c ci altfel'(X) =c ,c2Fp . Cumc1;:::;cr n u sun t toµi egali
exist s astfel încât ccs6= 0 . Cumess divideccs6= 0 rezult  c  grad s= 0 .
Con tradicµie.
15

16
Deducem c  'p'= (ck)pck0( mo dek
k) , adic ek
kdivide p e'p' p en tru
oricek . Cum sun t prime în tre ele, f(X)j'(X)p'(X) .
Recipro c, presupunem c  exist  '(X)2Fp[X] astfel încât f(X) divide'(X)p'(X)
³i1grad ' (X)< n . Cum eviden t ('(X)i;'(X)j) = 1 oricare ar  i; j2Fp ,
i6=j , a v em, folosind 3.1 ³i (c;ab) = (c;a)(c;b) dac  (a;b) = 1
f(X) = (f(X);'(X)p'(X)) =p1Y
k=0(f(X);'(X)k): (3.2)
Cum8k2Fp ,'(x)k6= 0 (deoarece grad '(X)1 ) ³i grad'(X)k < n , rezult 
c  în 3.2 a v em cel puµin doi factori netriviali ai lui f , e ace³tia (f(X);'(X)i) ³i
(f(X);'(X)j) cui6=j .
Fie ³i0divizori monici ireductibili p en tru p olinom ul (f(X);'(X)i) , resp ectiv
(f(X);'(X)j) . Dac =0, atunci divide p e'(X)i ³i'(X)j , deci p eij6= 0 .
Con tradicµie. Deci 6=0³i eviden t ³i0sun t divizori ai lui f .
Prezen t m acum o meto d  de determinare a un ui p olinom '2Fp[X] , grad' < n
astfel încât un p olinom monic dat f2Fp[X] de gradn>1 s  divid  p e '(X)p'(X) .
Presupunem c 
'(X) =c0+c1X+:::+cn1Xn12Fp[X]:
A tunci
'(X)p= (c0+c1X+:::+cn1Xn1)p=cp
0+cp
1Xp+:::+cp
n1X(n1)p
=c0+c1Xp+:::+cn1X(n1)p:
Aplicând teorema împ rµirii cu rest, putem scrie
Xip=f(X)qi(X) +ri(X);0in
cu
qi(X); ri(X)2Fp[X]; ri(X) =ri0+ri1X+:::+rin1Xn1:
Deducem c 
'(X)p'(X) =n1X
i=0ci(ri(X)Xi) +f(X)q(X)
undeq(X)2Fp[X] . Decif(X) divide p olinom ul '(X)p'(X) dac  ³i n umai dac 
divide p olinom ul h(X) =Pn1
i=0ci(ri(X)Xi) . Dar gradh(X)<n , decif(X) divide p e
'(X)p'(X) dac  ³i n umai dac  h(X) = 0 . Punând condiµia ca co ecienµii p olinom ului
h s  e egali cu 0 , deducem c  f(X) divide p e'(X)p'(X) dac  ³i n umai dac 
co ecienµii c0;c1;:::;cn1 ai p olinom ului '(X) constituie o soluµie a sistem ului omogen
cu co ecienµi în Fp .
(c0;c1;:::;cn1)(RIn) = (0;0;:::0) (3.3)
16

17
unde
R=0
BBB@r00r01


r0;n1
r10r11


r1;n1
…
rn1;0rn1;1


rn1;n11
CCCA2Mn(Fp);
In=0
BBB@1 0
1
. . .
0 11
CCCA2Mn(Fp):
Dac '(X) =c0; c02Fp , atunci'(X)p'(X) =cp
0c0=c0c0= 0: Decif(X)
divide p e'(X)p'(X) în acest caz, de unde rezult  c  sistem ul (3.3) admite în totdeauna
soluµiile (c0;0;:::; 0) ,c02Fp .
Observ  m c  sistem ul (3.3) admite n umai soluµiile (c0;0;:::; 0) ,c02Fp dac  ³i n umai
dac  rangul matricei RIn esten1 , ceea ce este ec hiv alen t cu faptul c  f admite un
singur divizor monic ireductibil (conform lemei 3.1) adic  f=e,e1 .
Fief2Fp[X] de gradn>1 . Dorim s  g sim un algoritm prin care s  determin m o
factorizare netrivial  a lui f înFp[X] când asemenea factoriz ri exist , sau în caz con trar
s  decidem c  f este ireductibil p este Fp .
Eviden t, putem presupune c  f este monic.
Mai m ult, putem presupune c  f0(X)6= 0 . În tr-adev  r, dac  f=Xn+an1xn1+
:::+a1X+a0 ³if0= 0 , atunciiai= 0 ,1i<n , ³in1 = 0 , de undeai= 0 oricare ar
1i<n ,p-i ³in=pm .
Deducem c 
f(X) = (Xm+:::+a2pX2+apX+a0)p(3.4)
deci a v em o factorizare netrivial  a lui f înFp[X]:
P e baza rezultatelor de mai sus Berlek amp a imaginat urmatorul algoritm care
reduce problema pus  la rezolv area un ui sistem de ecuaµii liniare p este Fp ³i la aarea
cmmdc a unor p olinoame din Fp[X] .
A lgoritmul lui Berlekamp:
Datf2Fp[X] , monic de grad n ,f0(X)6= 0 se construie³te matricea Q=RIn2
Mn(Fp) . Dac  rang Qn2 se p oate aa o soluµie (c0;c1;:::;cn1) a sistem ului 3.3 cu
cel puµin un ci6= 0 p en tru un indice i ,1in . Dac '(X) =c0+c1X1+:::+cn1Xn1,
atunci 1 gradj(X)<n ³i
f(X) =p1Y
k=0(f(X);'(X)k)
este o factorizare netrivial  a lui f(X) înFp[X] .
Dac  rangQ=n1 , atuncif admide un singur divizor monic ireductibil 2Fp[X]
³if=ecue2N.
Cum 06=Df(X) =ee10rezult  c p-e ³i06= 0 .
Dar ind ireductibil rezult  c  (;0) = 1 , deci (f(X);f0(X)) =e1. A v eme= 1
17

18
(adic f este ireductibil) dac  ³i n umai dac  (f(X);f0(X)) = 1 . Astfel p olinom ul  se
a  împ rµind p e f(X) la(f(X);f0(X)) , iar ap oi se a  e împ rµind p e n la grad , deci
factorizarea f(X) =e,e1 este complet determinat .
Exemplu 3.2. Fief=X5+X+ 12F2[X] . S  se desc ompun  p olinomul f în pr o dus
de factori ir e ductibili în inelul F2[X] .
Soluµie . S  determin m matricea Q . A v em
8
>>>>>><
>>>>>>:X0=f(X)
0 + 1
X2=f(X)
0 +X2
X4=f(X)
0 +X4
X6=f(X)
X+X+X2
X8=f(X)
X3+X3+X4)Q=RI5=0
BBBB@0 0 0 0 0
0 1 1 0 0
0 0 1 0 1
0 1 1 1 0
0 0 0 1 01
CCCCA:
Se observ   c  rang Q =3 deci exist  un p olinom '(X)2F2[X] ,1 grad'<5 , astfel
încâtf(X)j'(X)2'(X) . P en tru determinarea un ui astfel de p olinom consider m
sistem ul
(c0;c1;c2;c3;c4)Q= (0;0;0;0;0)
care explicit se scrie 8
>>>><
>>>>:c1+c3= 0
c1+c2+c3= 0
c3+c4= 0
c2= 0
³i soluµia general  este (;; 0;; ) cu;2F2 . Luând= 0 ³i= 1 , g sim
'(X) =X4+X3+X .
A v em:
f(X) = (f;'2') = (f;')(f;'1) = (X5+X+1;X4+X3+X)
(X5+X+1;X4+X3+X+1) = (X3+X2+1)(X2+X+1):
Cum p olinoamele X3+X2+1 ³iX2+X+1 n u admit r d cini în F2 ele sun t ireductibile
p esteF2 , deci
f(X) = (X3+X2+ 1)(X2+X+ 1)
reprezin t  c hiar o descompunere în factori ireductibili p este F2 p en tru p olinom ul f .
Exemplu 3.3. Fieg(X) =X12+ 2X9+ 2X6+X3+ 12F3[X] .
S  se desc ompun  p olinomul g în pr o dus de factori ir e ductibili în inelul F3[X] .
Soluµie. Se observ   c  toµi exp onenµii lui X care apar în scrierea canonic  a lui g ,
sun t divizibili prin 3, deci g0(X) = 0 ³ig(X) = (X4+ 2X3+ 2X2+X+ 1)3.
Fief(X) =X4+ 2X3+ 2X2+X+ 1 . A v emf0(X) =X3+X+ 16= 0:
18

19
Aplic m algoritm ul lui Berlek amp p olinom ului f . P en tru a aa matricea Q , scriem
8
>>>><
>>>>:X0=f(X)
0 + 1
X3=f(X)
0 +X3
X6=f(X)
(X2+X+ 2) + 1 + 2 X3
X9=f(X)
(X5+X4+ 2X3+ 2X+ 1) + 2 + 2 X3)Q=0
BB@0 0 0 0
0 2 0 1
1 0 2 2
2 0 0 11
CCA:
Se observ   c  rang Q= 3 decif(X) =eunde2F3[X] , p olinom monic ireductibil
³ie2N. A m p olinom ul  ³i n um rul e . Aplicând algoritm ul lui Euclid g sim
(f(X);f0(X)) = (X4+ 2X3+ 2X2+X+ 1;X3+X+ 1) =X2+X+ 2:
P olinom ul este câtul lui f(X) prin ((f(X);f0(X))) =X2+X+ 2 ³i g sim=
X2+X+ 2 . A³adarf(X) = (X2+X+ 2)e³i cumf are gradul 4 rezult  c e= 2 .
Descompunerea c utat  este:
g(X) =f(X)3= (X2+X+ 2)6:
19

Capitolul 4
P olinoame ireductibile p este Fq[X]
T eorem  4.1. Pentru oric e c orp nit Fq ³i oric en2N , pr o dusul tutur or p olino amelor
monic e ir e ductibile p este Fq ale c  r or gr ade divid p e n este e gal cu xqnx:
Demonstr aµie. Fieg=Q
djnff2Fq[X]j gradf=d;f monic;f ireductibilg ³i vrem
s  ar t m c  g=xqnx . P en tru demonstraµia acestui fapt ne v om a juta de lema
urm toare:
Lem  4.2. Oric e p olinom monic ir e ductibil f2Fq[X] cu gr adf=d ar e to ate r  d cinile
înFqd (ind de forma ;q;q2;:::;qd1)
Demonstr aµie. Fief=Pd
i=0aixicuai2Fq .
Dac f() = 0 atunciPd
i=0aii= 0 . În trucât ridicarea la puterea q este morsm (este
o putere a automorm ului F rob enius), obµinem c Pd
i=0aq
i(q)i= 0
)f(q) = 0:
Am demonstrat:  r d cin  p en tru f implic qr d cin  p en tru f . Pro cedând
analog, ar t m c  q2;q3:::;qd1sun t r d cini ale lui f . P e de alt  parte, Fq[X]=(f)
este corp cu qdelemen te în care X+ (f) este r d cin , adic  f are o r d cin   înFqd .
Ar t m c  g=Q
djnff2Fq[X]j gradf=d;f monic;f ireductibilg are ca r d cini
elemen tele lui Fqn .
Fie r d cin  a lui g)9f2Fq[X];f() = 0 ,f este ireductibil de grad d , monic.
Conform lemei an terioare rezult  c  f are toate r d cinile în FqdFqn , deci2Fqn .
Recipro c,82Fqn ,Irr(;Fq) este ireductibil; grad Irr(;Fq) = [Fq() :Fq] . Fie
³irul de extinderi FqFq()Fqn , unde [Fq() :Fq] =d ³i[Fqn:Fq] =n , atuncidjn .
Deci gradul p olinom ului minimal al lui  p esteFq ,Irr(;Fq) , estedjn .
Observ  m c  g are r d cini distincte p en tru c :
8f2Fq[X] ,f ireductibil)f n u are r d cini m ultiple.
Prin reducere la absurd presupunem c  f ar a v ea r d cini m ultiple, atunci (f;f0)6= 1 .
20

21
Cumf este ireductibil ³i grad f0< gradf , atuncif0= 0 . A v em
f0= (dX
i=0aixi)0=dX
i=0iaixi1= 0)iai= 0;80id:
Relaµiaiai= 0 ,8i implic pji sauai= 0 , decif=a0+apxp+a2px2p+::: .
Fie':Fq!Fq ,'(x) =xp(automorsm ul lui F rob enius) , rezult  c  oricare ar 
i , exist bi cuai=bip, decif=bp
0+bp
pxp+:::= (b0+bpx+:::)pn u este ireductibil.
Con tradicµie.
 Dac f1;f2 apar in pro dusul care dene³te p e g , atunci (f1;f2) = 1 .
Dar ³iXqnX are ca r d cini toate elemen tele lui Fqn , deci am ar tat c  g=XqnX:
Corolar 4.3. Fieq un num r prim ³i n2N . Dac  Nq(d) este num rul p olino amelor
monic e ir e ductibile de gr ad d dinFq[X] , atunci
qn=X
djndNq(d) (4.1)
Demonstr aµie. FiePd=ff2Fq[X]jf ireductibil; monic; gradf =dg . Conform
teoremei an terioare a v em c Q
djnPd=XqnX . T recând la grade în aceast  form ul 
rezult  c P
djndjPdj=qn, unde conform notaµiilor noastre, jPdj=Nq(d) .
Din 4.1 v om putea determina o form ul  explicit  p en tru n um rul de p olinoame monice
ireductibile de grad d dinFq[X] . A v em nev oie de o funcµie aritmetic , n umit  funcµia lui
Mo bius .
Un n um r natural n>1 se n ume³te lib er de p  tr ate dac n este prim sau pro dus de
n umere prime distincte.
Deniµie 4.4. Aplic aµia:N!C denit  prin
(n) =8
><
>:1; dac  n= 1;
(1)k; dac  n este pr o dus de k numer e prime distincte ;
0; dac  n>1 ³in nu este lib er de p  tr ate :
se nume³te funcµia lui M  o bius .
Lem  4.5. Dac  n>1 , atunciP
djn(d) = 0 , unded p ar cur ge toµi divizorii natur ali ai lui
n .
Demonstr aµie. Presupunem c  n=pe1
1pe2
2:::pek
k, undep1;p2;:::;pk sun t n umere prime
distincte,ei2N,1k . În sumaP
djn(d) ne putem m rgini doar la urm toarele v alori
ale luid :1;pi;1ik;pipj cu1i<jk în totalC2
k;:::;p1p2:::pk .
21

22
A v em:
X
djn(d) =(1) +kX
i=1(pi) +X
1i<jk(pipj) +:::+(p1p2:::pk)
= 1 +C1
k(1) +C2
k(1)2+


+Ck
k(1)k
= (1 + (1))k= 0:
T eorem  4.6. ( formula de inversiune a lui M  o bius )
(i) Cazul aditiv: Fie h:N!G , eH:N!G , unde (G;+) este un grup ab elian.
A tunci
H(n) =X
djnh(d);8n2N (4.2)
dac   ³i numai dac  
h(n) =X
djnn
d
H(d) =X
djn(d)Hn
d
p entru toµi n2N: (4.3)
(ii) Cazul multiplic ativ: Fie h:N!G , eH:N!G , unde (G;
) este un grup
ab elian. A tunci
H(n) =Y
djnh(d);8n2N (4.4)
dac   ³i numai dac  
h(n) =Y
djnH(d)(n
d)=Y
djnHn
d(d)
p entru toµi n2N: (4.5)
Demonstr aµie. (i) Cândd parcurge m ulµimea divizorilor naturali ai lui n , atuncin
dpar-
curge aceea³i m ulµime, deci egalitateaP
djn
n
d
H(d) =P
djn(d)H
n
d
este adev  rat .
Presupunând 4.2 adev  rat  ³i utilizând lema 4.5, a v em:
X
djnn
d
H(d) =X
djn(d)Hn
d
=X
djn(d)X
cjn
dh(c)
=X
cjnX
djn
c(d)h(c) =X
cjnh(c)X
djn
c(d) =h(n)
c ciP
djn
c(d)6= 0 n umai dac  c=n .
(ii) Demonstraµia p rµii (ii) urmeaz  imediat din demonstraµia p rµii (i) dac  înlo-
cuim sumele cu pro duse ³i m ultiplii cu puteri.
22

23
T eorem  4.7. Num rulNq(n) al p olino amelor monic e ir e ductibile de gr ad n din Fq[X]
este dat de
Nq(n) =1
nX
djnn
d
qd=1
nX
djn(d)qn
d:
Demonstr aµie. Aplic m cazul aditiv al form ulei de in v ersiune a lui M o bius luândG=Z ,
h(n) =nNq(n) ³iH(n) =qnp en tru toµi n2N .
Exemplu 4.8. (1)N2(8) =1
8((1)28+(2)24+(4)22+(8)2) =1
8(2824) = 30;
de ci exist  30 de p olino ame monic e ir e ductibile de gr ad 8 în F2[X] .
(2)N3(5) =1
5((1)35+(5)3) =1
5(353) = 24 ,
de ci exist  24 de p olino ame monic e ir e ductibile de gr ad 5 în F3[X] .
Ca o alt  aplicaµie a form ulei de in v ersiune a lui M o bius, putem stabili o form ul 
explicit  p en tru cel de-al n -lea p olinom ciclotomic n .
T eorem  4.9. FieK un c orp de c ar acteristic   p ³in2N ,p-n . A tunci al n -le a p olinom
ciclotomic n p esteK satisfac e
n(X) =Y
djn(Xd1)(n
d)=Y
djn(Xn
d1)(d):
Demonstr aµie. Se aplic  cazul m ultiplicativ al form ulei de in v ersiune a lui M o bius p en tru
grupul m ultiplicativ G al funcµiilor raµionale diferite de zero p este K . Fieh(n) = n(X)
³iH(n) =Xn1 p en tru8n2N . Conform prop oziµiei 2.11 (b) a v emQ
djnd=Xn1 ,
deci egalitatea 4.4 este satisf cut  ³i astfel 4.5 ne d  rezultatul dorit.
Exemplu 4.10. Pentru c orpurile K p este c ar e 12 este denit, avem
12(X) =Y
dj12(X12
d1)(d)
= (X121)(1)(X61)(2)(X41)(3)(X31)(4)(X21)(6)(X1)(12)
=(X121)(X21)
(X61)(X41)=X4X2+ 1:
23

Bibliograe
[1] V olf Aurelian Claudiu, T ofan Ioan, Inele. Mo dule.T e orie Galois , Editura Matrix-
Rom, Bucure³ti, 2001.
[2] Ion. D. Ion, T. Albu, Itiner ar în algebr a sup erio ar   , Editura All,1997.
24