Лекции по прикладной алгебре. v1.0 (1127110), страница 5
Текст из файла (страница 5)
Òîãäà ìíîãî÷ëåí f (x) èìååò â Fnp êîðåíü x, àíîðìèðîâàííûé f (x) ÿâëÿåòñÿ ìèíèìàëüíîé ôóíêöèåé äëÿ íåãî.nÊðîìå òîãî, x ÿâëÿåòñÿ êîðíåì óðàâíåíèÿ xp −1 − 1.nÏî ñâîéñòâàì ì.ì., xp −1 − 1 äåëèòñÿ íà f (x).Ïðèêëàäíàÿ àëãåáðà52 / 225Ïîëÿ Ãàëóà - IÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì...Èñïîëüçóÿ ýòó òåîðåìó, ìû ìîæåì çàâåðøèòü ðàçëîæåíèåx15 +1 = (x+1)(x2 +x+1)(x4 +x+1)(x4 +x3 +1)(x4 +x3 +x2 +x+1) ,ïåðåáèðàÿ íåïðèâîäèìûå ìíîãî÷ëåíû èç4(ò.ê.
x(x15 + 1) = x2 + x).F42Òåîðåìàn −1Ëþáîé íåïðèâîäèìûé äåëèòåëü ìíîãî÷ëåíà xpñòåïåíü, íå ïðåâîñõîäÿùóþ n.− 1 èìååòÏðèêëàäíàÿ àëãåáðà52 / 225Ïîëÿ Ãàëóà - IÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì...Èñïîëüçóÿ ýòó òåîðåìó, ìû ìîæåì çàâåðøèòü ðàçëîæåíèåx15 +1 = (x+1)(x2 +x+1)(x4 +x+1)(x4 +x3 +1)(x4 +x3 +x2 +x+1) ,ïåðåáèðàÿ íåïðèâîäèìûå ìíîãî÷ëåíû èç4(ò.ê. x(x15 + 1) = x2 + x).F42Òåîðåìàn −1Ëþáîé íåïðèâîäèìûé äåëèòåëü ìíîãî÷ëåíà xpñòåïåíü, íå ïðåâîñõîäÿùóþ n.− 1 èìååòÄîêàçàòåëüñòâîÏóñòü ϕ íåïðèâîäèìûé ìíîãî÷ëåí ñòåïåíè k , êîòîðûénÿâëÿåòñÿ äåëèòåëåì xp −x. Êðàòíûå ϕ îáðàçóþò ìàêñèìàëüíûéèäåàë â êîëüöå Fp [x], ïîýòîìó êîëüöî âû÷åòîâ ïî ýòîìó èäåàëóÿâëÿåòñÿ ïîëåì.Ïðèêëàäíàÿ àëãåáðà53 / 225Ïîëÿ Ãàëóà - IÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì...Ïîëå ìîæíîn ðàññìàòðèâàòüo êàê âåêòîðíîå ïðîñòðàíñòâî íàä n Fp ñk−1áàçèñîì 1, x, .
. . , x. Îáîçíà÷èì x = α. Ïîñêîëüêó xp − xäåëèòñÿ íà ϕ, òî â êîëüöå âû÷åòîâ ïî ìîäóëþ èäåàëà (ϕ) ïîëó÷àåìnαp − α = 0.Ëþáîé ýëåìåíò ïîñòðîåííîãî ïîëÿ âûðàæàåòñÿ ÷åðåç áàçèñ: β =Pk−1ini=0 ai α . Âîçâåäÿ îáå ÷àñòè ýòîãî ðàâåíñòâà â ñòåïåíü p , ïîëó÷èìnnβ p = (a0 + a1 α + . . . + ak−1 αk−1 )p =nnnnn= ap0 + ap1 αp + . . . + apk−1 (αk−1 )p == a0 + a1 α + . . . + ak−1 αk−1 = β .nnÎòñþäà β p − β = 0, ò.å. β êîðåíü óðàâíåíèÿ xp − x = 0.
Íî óíåãî íå áîëåå pn ðàçëè÷íûõ êîðíåé, à â ïîñòðîåííîì íàìè ïîëå pkýëåìåíòîâ. Êàæäûé ýëåìåíò ïîëÿ ÿâëÿåòñÿ êîðíåì, ∴ n > k .Ïðèêëàäíàÿ àëãåáðàÏîëÿ Ãàëóà - IÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì...ÓòâåðæäåíèåÏóñòü β ∈ Fnp èìååò ïîðÿäîê l, à åãî ì.ì. m(x) èìååò ñòåïåíü k ...Òîãäà (a) pk − 1 .. l, à åñëè r < k , òî (b) (pr − 1) 6 .. l.54 / 225Ïðèêëàäíàÿ àëãåáðàÏîëÿ Ãàëóà - IÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì...ÓòâåðæäåíèåÏóñòü β ∈ Fnp èìååò ïîðÿäîê l, à åãî ì.ì. m(x) èìååò ñòåïåíü k ...Òîãäà (a) pk − 1 ..
l, à åñëè r < k , òî (b) (pr − 1) 6 .. l.Äîêàçàòåëüñòâîa) Ïî íåïðèâîäèìîìó ìíîãî÷ëåíó k -é ñòåïåíè m(x) ñòðîèì ïîëåèç pk ýëåìåíòîâ. Âñå åãî íåíóëåâûå ýëåìåíòû, â òîì ÷èñëå è β ,kÿâëÿþòñÿ êîðíÿìè óðàâíåíèÿ xp −1 − 1 = 0, ò.å.kkβ p −1 − 1 = 0 è β p −1 = 1..b) Ïóñòü (pr − 1) .. l è r < k . Òîãäà β êîðåíü óðàâíåíèÿ.rrxp − 1 = 0, à ò.ê. m(x) ì.ì. äëÿ β , òî (xp − 1)..m(x) (áûëîräîêàçàíî). Ìû íàøëè íåïðèâîäèìûé äåëèòåëü ìíîãî÷ëåíà xp −1 ñòåïåíè k , íî k > r, ÷òî ïðîòèâîðå÷èò äîêàçàííîìó ðàíåå.54 / 225Ïðèêëàäíàÿ àëãåáðàÏîëÿ Ãàëóà - IÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì...Ñëåäóþùàÿ òåîðåìà íóæíà íàì äëÿ òîãî, ÷òîáû ðàñêëàäûâàòüìíîãî÷ëåíû íà ìíîæèòåëè.ÒåîðåìàÏóñòü β ∈ Fnp êîðåíü íåïðèâîäèìîãî ìíîãî÷ëåíà ϕ(x) ñòåïåíèn−1n ñ êîýôôèöèåíòàìè èç Fp .
Òîãäà β, β p , . . . , β pâñå ðàçëè÷íûè èñ÷åðïûâàþò ñïèñîê êîðíåé ýòîãî ìíîãî÷ëåíà.Ò. å. ÷òîáû ïîëó÷èòü âñå êîðíè íåïðèâîäèìîãî ìíîãî÷ëåíà,äîñòàòî÷íî íàéòè îäèí èç íèõ è âîçâîäèòü åãî ïîñëåäîâàòåëüíîâ ñòåïåíü p.55 / 225Ïðèêëàäíàÿ àëãåáðàÏîëÿ Ãàëóà - IÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì...Ñëåäóþùàÿ òåîðåìà íóæíà íàì äëÿ òîãî, ÷òîáû ðàñêëàäûâàòüìíîãî÷ëåíû íà ìíîæèòåëè.ÒåîðåìàÏóñòü β ∈ Fnp êîðåíü íåïðèâîäèìîãî ìíîãî÷ëåíà ϕ(x) ñòåïåíèn−1n ñ êîýôôèöèåíòàìè èç Fp . Òîãäà β, β p , .
. . , β pâñå ðàçëè÷íûè èñ÷åðïûâàþò ñïèñîê êîðíåé ýòîãî ìíîãî÷ëåíà.Ò. å. ÷òîáû ïîëó÷èòü âñå êîðíè íåïðèâîäèìîãî ìíîãî÷ëåíà,äîñòàòî÷íî íàéòè îäèí èç íèõ è âîçâîäèòü åãî ïîñëåäîâàòåëüíîâ ñòåïåíü p.ÄîêàçàòåëüñòâîÂíà÷àëå äîêàæåì, ÷òî åñëè β êîðåíü ϕ(x), òî β p òîæåêîðåíü.55 / 225Ïðèêëàäíàÿ àëãåáðà56 / 225Ïîëÿ Ãàëóà - IÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì...Êàê áûëî ïîêàçàíî âûøå, ap = a äëÿ âñåõ a ∈ Fp . Ïîýòîìó äëÿëþáîãî ìíîãî÷ëåíà f (x) ñ êîýôôèöèåíòàìè èç Fp âûïîëíÿåòñÿðàâåíñòâî(f (x))p = f (xp ) .(∗)Äåéñòâèòåëüíî, âîçâåäåíèå â ñòåïåíü p ñîõðàíÿåò îïåðàöèèñëîæåíèÿ è óìíîæåíèÿ.
Ïîýòîìó(a0 + a1 x + . . . + ak xk )p = ap0 + ap1 xp + ap2 x2p + . . . + apk xkp == a0 + a1 (xp ) + a2 (xp )2 + . . . + ak (xp )k .Åñëè ϕ(β) = 0, òî è ϕ(β)p = 0. Èç (∗) ïîëó÷àåì, ÷òî è ϕ(β p ) = 0.n−1Èòàê, ìû äîêàçàëè, ÷òî β, β p , . . . , β p êîðíè ìíîãî÷ëåíà ϕ(x).Ïðèêëàäíàÿ àëãåáðà57 / 225Ïîëÿ Ãàëóà - IÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì...Îñòàëîñü äîêàçàòü, ÷òî îíè âñå ðàçëè÷íû, òîãäà èç äîêàçàííîãîðàíåå áóäåò ñëåäîâàòü, ÷òî ìû íàøëè âñå êîðíè ìíîãî÷ëåíàϕ(x).lkÏðåäïîëîæèì, ÷òî β p = β p , ïðè÷åì áåç îãðàíè÷åíèÿ îáùíîñòènl 6 k .
Ìû çíàåì, ÷òî β p = β . Ñ äðóãîé ñòîðîíû, ïîñêîëüêónβp = βpk ·pn−k k pn−k l pn−kn−k+l= βp= βp= βp,n−k+l−1 −1 = 0. Èç ðàíåå äîêàçàííîãîòî β êîðåíü óðàâíåíèÿ xpïîëó÷àåì n − k + l > n, òàê ÷òî l > k . Äðóãèìè ñëîâàìè, l = kè âñå âûïèñàííûå âûøå êîðíè ðàçëè÷íû.Ïðèêëàäíàÿ àëãåáðàÏîëÿ Ãàëóà - IÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì: ðåøåíèå óðàâíåíèéÏðèìåðÐàññìîòðèì F2 è íåïðèâîäèìûé íàä ýòèì ïîëåì ìíîãî÷ëåíx4 + x3 + 1. Íàéäåì åãî êîðíè â ðàñøèðåíèè F42 .Îäèí êîðåíü ïîëó÷àåì íåìåäëåííî: x.Ïî òîëüêî ÷òî äîêàçàííîé òåîðåìå ìîæíî âûïèñàòü îñòàëüíûå:x2 , x4 = x3 + 1, x8 = x6 + 1 = x3 + x2 + x.58 / 225Ïðèêëàäíàÿ àëãåáðà58 / 225Ïîëÿ Ãàëóà - IÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì: ðåøåíèå óðàâíåíèéÏðèìåðÐàññìîòðèì F2 è íåïðèâîäèìûé íàä ýòèì ïîëåì ìíîãî÷ëåíx4 + x3 + 1.
Íàéäåì åãî êîðíè â ðàñøèðåíèè F42 .Îäèí êîðåíü ïîëó÷àåì íåìåäëåííî: x.Ïî òîëüêî ÷òî äîêàçàííîé òåîðåìå ìîæíî âûïèñàòü îñòàëüíûå:x2 , x4 = x3 + 1, x8 = x6 + 1 = x3 + x2 + x.Ïîêàæåì, ÷òî α = x2 äåéñòâèòåëüíî êîðåíü x4 + x3 + 1 = 0.Ïîäñòàâëÿåì:x4 + x3 + 1 |x=α = x4·2 + x4+2 + 1 |x4 =x3 +1 == (x3 + 1)2 + (x3 + 1)x2 + 1 = (x6 + 1) + x5 + x2 + 1 == x6 + x5 + x2 = x2 (x4 + x3 + 1) = x2 · 0 = 0.Ïðèêëàäíàÿ àëãåáðàÏîëÿ Ãàëóà - IÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÊàê ðåøàòü óðàâíåíèÿ, êîãäà êîðíåé íåò59 / 225Ïðèêëàäíàÿ àëãåáðà59 / 225Ïîëÿ Ãàëóà - IÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÊàê ðåøàòü óðàâíåíèÿ, êîãäà êîðíåé íåòÄëÿ ðåøåíèÿ óðàâíåíèÿf (x) = 0 ,(∗)ãäå f íåïðèâîäèìûé ìíîãî÷ëåí ñòåïåíè n, íàä ïîëåìíóæíî ïîñòðîèòü ïîëå Fp [x]/(f ).Êîðíè (∗) â ýòîì ïîëå: x, x2 , . . .
, xpn−1. îáùåì ñëó÷àå äëÿ ðåøåíèÿ óðàâíåíèÿ íóæíî óìåòüðàñêëàäûâàòü ìíîãî÷ëåí íà íåïðèâîäèìûå ìíîæèòåëè.FpÏðèêëàäíàÿ àëãåáðà60 / 225Ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èçpnýëåìåíòîâÐàçäåë I1Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà - IÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏîñòðîåíèå ïîëåé ÃàëóàËèíåéíàÿ àëãåáðà íàä êîíå÷íûì ïîëåìÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåì2Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èç pnýëåìåíòîâÖèêëè÷åñêèå ïîäïðîñòðàíñòâàÇàäà÷è3Êîäû, èñïðàâëÿþùèå îøèáêèÎñíîâíàÿ çàäà÷à òåîðèè êîäèðîâàíèÿÖèêëè÷åñêèå êîäûÏðèêëàäíàÿ àëãåáðà61 / 225Ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èçpnýëåìåíòîâÐàçäåë IIÊîäû Á×Õ4Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿêîìáèíàòîðíûõ çàäà÷5×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎïåðàöèè íàä ÷.ó. ìíîæåñòâàìèËèíåàðèçàöèÿ6Àëãåáðàè÷åñêèå ðåø¼òêèÐåø¼òêèÏðèêëàäíàÿ àëãåáðà62 / 225Ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èçpnýëåìåíòîâÌóëüòèïëèêàòèâíàÿ ãðóïïà ðàñøèðåíèÿ ïîëÿÏðèìåð (ïîëåF42 )Ïîëå F42 ìîæíî ñòðîèòü ñ ïîìîùüþ ëþáîãî èç òðåõíåïðèâîäèìûõ ìíîãî÷ëåíîâ (íî ïîêà íå äîêàçàíî).Óäîáíåå âñåãî ýòî ñäåëàòü, åñëè âçÿòü ìíîãî÷ëåí f = x4 + x + 1(ïî÷åìó?).Áóäåì çàäàâàòü ýëåìåíòû ðàñøèðåíèÿ íàáîðàìè êîýôôèöèåíòîâìíîãî÷ëåíà, êîòîðûé ïîëó÷àåòñÿ â îñòàòêå ïðè äåëåíèè íà f ,çàïèñûâàÿ èõ â ïîðÿäêå âîçðàñòàíèÿ ñòåïåíåé.Ïîðîæäàþùèì ÿâëÿåòñÿ ýëåìåíò α = x, êîòîðûé çàïèñûâàåòñÿêàê (0, 1, 0, 0).Âû÷èñëèì ñòåïåíè α, ñâåäÿ ðåçóëüòàòû â òàáëèöó.Ïðèêëàäíàÿ àëãåáðà63 / 225Ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èçpnýëåìåíòîâÌóëüòèïëèêàòèâíàÿ ãðóïïà ïîëÿF42 ∼= F2 [x]/(x4 + x + 1)ñòåïåíü αα=α2 =α3 =1 + α = α4 =α + α2 = α5 =α2 + α3 = α6 =3α + α + 1 = α3 + α4 = α7 =1 + α2 = α + 1 + α2 + α = α8 =α + α3 = α9 =22α + 1 + α = α + α4 = α10 =α + α2 + α3 = α11 =231 + α + α + α = α2 + α3 + α4 = α12 =1 + α2 + α3 = α + α2 + α3 + α4 = α13 =1 + α3 = α + α3 + α4 = α14 =1 = α + α4 = α15 =1(0,(0,(0,(1,(0,(0,(1,(1,(0,(1,(0,(1,(1,(1,(1,x1,0,0,1,1,01,0,1,1,1,1,0,0,0,x20,1,0,0,1,1,01,0,1,1,1,1,0,0,x30)0)1)0)0)1)1)0)1)0)1)1)1)1)0)Ïðèêëàäíàÿ àëãåáðà64 / 225Ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èçpnýëåìåíòîâÈìåÿ òàêóþ òàáëèöó, î÷åíü ïðîñòî ïðîèçâîäèòü óìíîæåíèå:(x3 + x + 1) · (x2 + x + 1) = x2 ,(1, 1, 0, 1) · (1, 1, 1, 0) = (0, 0, 1, 0)α7 α10 = α17 = α2 .− (+mod 2 ) ,Ïðèêëàäíàÿ àëãåáðà65 / 225Ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èçpnýëåìåíòîâËåììàÏóñòü m ìàêñèìàëüíûé ïîðÿäîê ýëåìåíòà â êîíå÷íîéàáåëåâîé ãðóïïå G.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
