Конечные поля (часть 1) (1127160), страница 8
Текст из файла (страница 8)
è åãî ñòåïåíü íå ïðåâîñõîäèò n.ÄîêàçàòåëüñòâîÐàññìîòðèì ñëåäóþùèå ýëåìåíòû ïîëÿ Fnp : 1, β, β 2 , . . . , β n èõ n + 1 øòóêà, à ðàçìåðíîñòü Fnp êàê âåêòîðíîãî ïðîñòðàíñòâàðàâíà n ⇒ ýòè ýëåìåíòû ëèíåéíî çàâèñèìû, ò.å. ñóùåñòâóþòòàêèå íå âñå ðàâíûå 0 êîýôôèöèåíòû c0 , . . . , cn , ÷òîc0 1 + c1 β + .
. . + cn β n = 0,⇒ β êîðåíü ìíîãî÷ëåíà f (x) = c0 + c1 x + . . . + cn xn .Ìèíèìàëüíûì ìíîãî÷ëåíîì äëÿ β áóäåò íåêîòîðûéíîðìèðîâàííûé íåïðèâîäèìûé äåëèòåëü f (x).ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì: ñâîéñòâàÒåîðåìàËþáîé íåíóëåâîé ýëåìåíò ïîëÿ Fnp ÿâëÿåòñÿ êîðíåìnìíîãî÷ëåíà xp −1 − 1, ò.å.nxp −1 − 1 = (x − β1 ) · .
. . · (x − βpn −1 ),nãäå β1 , . . . , βpn −1 = Fn∗p = Fp r {0}.67 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì: ñâîéñòâàÒåîðåìàËþáîé íåíóëåâîé ýëåìåíò ïîëÿ Fnp ÿâëÿåòñÿ êîðíåìnìíîãî÷ëåíà xp −1 − 1, ò.å.nxp −1 − 1 = (x − β1 ) · . . . · (x − βpn −1 ),nãäå β1 , . . . , βpn −1 = Fn∗p = Fp r {0}.ÄîêàçàòåëüñòâîFn∗p öèêëè÷åñêàÿ ãðóïïà ïî óìíîæåíèþ ïîðÿäêàpn − 1.Ïîðÿäîê deg α ëþáîãî å¼ ýëåìåíòà (= ïîðÿäîê öèêëè÷åñêîéïîäãðóïïû hαi ïî òåîðåìå Ëàãðàíæà) äåëèò ïîðÿäîê ãðóïïû.Ïîýòîìó pn − 1 = q · deg α, αdeg α = 1 èαpn −1− 1 = αq deg α − 1 = (αdeg α )q − 1 = 1q − 1 = 0.67 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà68 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì: ñâîéñòâà...Êñòàòè èç òåîðåìû ñëåäóåò åù¼ îäèí ñïîñîá íàõîæäåíèÿîáðàòíûõ ýëåìåíòîâ â ïîëåÏðèìåðxpn −1Fnp , óäîáíûé ïðè íåáîëüøèõF = F2 [x]/ x3 + x + 1α = x + 1.Èìååì:|F | = 8, x3 = x + 1, ïîëån −2= 1 ⇒ xppèn:= x−1 .íàéòè ýëåìåíò, îáðàòíûé ê2α−1 = α−6 = (x+1)6 = (x+1)2 ·(x+1)2 = (x4 +1)(x2 +1) == (x2 + x + 1)(x2 + 1) = x4 + x3 + 6 x2 + 6 x2 + x + 1 == (x2 + x) + (x + 1) + x + 1 = x2 + x.Ïðîâåðêà:(x + 1)(x2 + x) = x(x + 1)2 = x(x2 + 1) == x3 + x = x + 1 + x = 1 .ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì: ñâîéñòâà...Ñëåäñòâèå (òåîðåìà Ôåðìà)Âñå ýëåìåíòû ïîëÿ Fnp (íå èñêëþ÷àÿ íóëÿ) ÿâëÿþòñÿ êîðíÿìènìíîãî÷ëåíà xp − x.69 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì: ñâîéñòâà...Ñëåäñòâèå (òåîðåìà Ôåðìà)Âñå ýëåìåíòû ïîëÿ Fnp (íå èñêëþ÷àÿ íóëÿ) ÿâëÿþòñÿ êîðíÿìènìíîãî÷ëåíà xp − x.ÄîêàçàòåëüñòâîÂûíåñåì x çà ñêîáêó:nxp − x = x xpn −1−1 .Ó âòîðîãî ñîìíîæèòåëÿ êîðíÿìè áóäóò âñå íåíóëåâûåýëåìåíòûïîëÿ, à ó ïåðâîãî 0.69 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì: ñâîéñòâà...Òåîðåìà êîëüöå ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåì..(xn − 1) .. (xm − 1) ⇔ n .. m.70 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì: ñâîéñòâà...Òåîðåìà êîëüöå ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåì..(xn − 1) .. (xm − 1) ⇔ n .. m.ÄîêàçàòåëüñòâîÏóñòü n = mk . Ñäåëàåì çàìåíó xm = y , òîãäàxn − 1 = y k − 1 è xm − 1 = y − 1. Äåëèìîñòü î÷åâèäíà,ò.ê.
1 êîðåíü y k − 1.70 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì: ñâîéñòâà...Òåîðåìà êîëüöå ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåì..(xn − 1) .. (xm − 1) ⇔ n .. m.ÄîêàçàòåëüñòâîÏóñòü n = mk . Ñäåëàåì çàìåíó xm = y , òîãäàxn − 1 = y k − 1 è xm − 1 = y − 1. Äåëèìîñòü î÷åâèäíà,ò.ê. 1 êîðåíü y k − 1..Ïðåäïîëîæèì, ÷òî n 6 .. m, ò.å. n = km + r, 0 < r < m,òîãäàxn − 1 =xr (xmk − 1)(xm − 1)+ xr − 1 =xm − 1xr (xmk − 1) m=(x − 1) + xr − 1.xm − 170 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì: ñâîéñòâà...Ïîñëåäíåå âûðàæåíèå çàäàåò ðåçóëüòàò äåëåíèÿ xn − 1 íàxm − 1 ñ îñòàòêîì, ïîñêîëüêó xmk − 1 äåëèòñÿ íà xm − 1 ïîäîêàçàííîìó âûøå.Îñòàòîê xr − 1 6= 0 â ñèëó ñäåëàííûõ ïðåäïîëîæåíèé.∴ xn − 1 íå äåëèòñÿ íà xm − 1.71 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà71 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì: ñâîéñòâà...Ïîñëåäíåå âûðàæåíèå çàäàåò ðåçóëüòàò äåëåíèÿ xn − 1 íàxm − 1 ñ îñòàòêîì, ïîñêîëüêó xmk − 1 äåëèòñÿ íà xm − 1 ïîäîêàçàííîìó âûøå.Îñòàòîê xr − 1 6= 0 â ñèëó ñäåëàííûõ ïðåäïîëîæåíèé.∴ xn − 1 íå äåëèòñÿ íà xm − 1.Òåîðåìà äà¼ò âîçìîæíîñòü ðàñêëàäûâàòü ìíîãî÷ëåíûïðè ñîñòàâíûõn.Íàïðèìåð, ðàçëîæèìx15x15 + 13â+ 1 = (x + 1)(x12F2 [x](ãäå96xn − 1−1 = +1):+ x + x + x3 + 1) ,x15 + 1 = (x5 + 1)(x10 + x5 + 1) .Âîçìîæíîñòü ðàñêëàäûâàòü ìíîãî÷ëåíû ñïåöèàëüíîãî âèäà íàíåïðèâîäèìûå äà¼ò ñëåäóþùàÿ òåîðåìà.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà72 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÐàçëîæåíèå ìíîãî÷ëåíîâ íà íåïðèâîäèìûåÒåîðåìàÂñå íåïðèâîäèìûå ìíîãî÷ëåíû n-é ñòåïåíè èçnìíîãî÷ëåí xp − x.Fp [x]äåëÿòÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà72 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÐàçëîæåíèå ìíîãî÷ëåíîâ íà íåïðèâîäèìûåÒåîðåìàÂñå íåïðèâîäèìûå ìíîãî÷ëåíû n-é ñòåïåíè èçnìíîãî÷ëåí xp − x.Fp [x]äåëÿòÄîêàçàòåëüñòâîn = 1. Óáåæäàåìñÿ, ÷òî (x − a) | (xp − x), ãäå a ∈ Fp : ïðè a = 0ýòî î÷åâèäíî, à â îñòàëüíûõ ñëó÷àÿõ äîêàçàíî, ÷òî a êîðåíü ìíîãî÷ëåíà xp−1 − 1 = (xp − x)/x.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà72 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÐàçëîæåíèå ìíîãî÷ëåíîâ íà íåïðèâîäèìûåÒåîðåìàÂñå íåïðèâîäèìûå ìíîãî÷ëåíû n-é ñòåïåíè èçnìíîãî÷ëåí xp − x.Fp [x]äåëÿòÄîêàçàòåëüñòâîn = 1. Óáåæäàåìñÿ, ÷òî (x − a) | (xp − x), ãäå a ∈ Fp : ïðè a = 0.ýòî î÷åâèäíî, à â îñòàëüíûõ ñëó÷àÿõ äîêàçàíî, ÷òî a êîðåíü ìíîãî÷ëåíà xp−1 − 1 = (xp − x)/x.n > 1 Ñòðîèì ïî íåïðèâîäèìîìó è (áåç îãðàíè÷åíèÿ îáùíîñòè íîðìèðîâàííîìó) ìíîãî÷ëåíó f (x) ñòåïåíè n ïîëå Fnp .n ýòîì ïîëå x êîðåíü è f (x), è xp −1 − 1, ïðè÷¼ìf (x) ì.ì. äëÿ íåãî.nÏî ñâîéñòâàì ì.ì. xp −1 − 1 äåëèòñÿ íà f (x).ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà73 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÏðèìåð: çàâåðøàåì ðàçëîæåíèåx15 + 1 ∈ F2 [x]4x15 + 1 = x2 −1 − 1, ïîýòîìó ïðîâåðÿåì ñòåïåíè p = 2 îò 1 äî 4:24 − 1 = 15|15, 23 − 1 = 7 6 |15, 22 − 1 = 3|15, 21 − 1 = 1|15,41x(x15 + 1) = x2 + x, îòêóäà âñå íåïðèâîäèìûå ìíîãî÷ëåíû4-é ñòåïåíè áóäóò äåëèòåëÿìè x16 − x è, ñëåäîâàòåëüíî,x15 + 1. Òàêèõ ìíîãî÷ëåíîâ 3:x4 + x + 1, x4 + x3 + 1 è x4 + x3 + x2 + x + 1.2x(x3 + 1) = x2 + x,22-é+ 1.îòêóäà âñå íåïðèâîäèìûå ìíîãî÷ëåíû4ñòåïåíè áóäóò äåëèòåëÿìè x3è, ñëåäîâàòåëüíî, x−xx2 + x + 1 .Òàêîé ìíîãî÷ëåí òîëüêî îäèí:31x(x1 + 1) = x2 + x,Èòîãî: ðàçëîæåíèåx15 +1=xx2 + x.îòêóäà åäèíñòâåííûé îòëè÷íûé îòíåïðèâîäèìûé ìíîãî÷ëåíx15 + 11-éñòåïåíèx+1äåëèòFíà íåðàçëîæèìûå íàä 2 ìíîãî÷ëåíû 2(x+1)(x +x+1)(x4 +x+1)(x4 +x3 +1)(x4 +x3 +x2 +x+1).ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà74 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì...ÒåîðåìàËþáîé íåïðèâîäèìûé ìíîãî÷ëåí-äåëèòåëü xpñòåïåíü, íå ïðåâîñõîäÿùóþ n.n −1− 1 èìååòÄîêàçàòåëüñòâînÏóñòü ϕ íåïðèâîäèìûé äåëèòåëü xp − x ñòåïåíè k .defÒîãäà F = Fp /(ϕ) ïîëå, êîòîðîån ðàññìîòðèì êàêo âåêòîðíîåk−1ïðîñòðàíñòâî íàä Fp ñ áàçèñîì 1, x, . . .
, x..nÎáîçíà÷èì x = α. Ïîñêîëüêó (xp − x) ..ϕ, òî â F èìååìnαp − α = 0.k−1PËþáîé ýëåìåíò F âûðàæàåòñÿ ÷åðåç áàçèñ: β =ai α i .i=0ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà75 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì...Âîçâåäÿ îáå ÷àñòè ýòîãî ðàâåíñòâà â ñòåïåíü pn , ïîëó÷èìk−1pnk−1PPnpiβ =ai α=ai α i = β ,i=0i=0ò.å.
β êîðåíü óðàâíåíèÿnxp − x = 0 .(∗)Èòàê, êàæäûé ýëåìåíò ïîëÿ F ÿâëÿåòñÿ êîðíåì (∗), íî ó (∗) íåáîëåå pn ðàçëè÷íûõ êîðíåé, à |F | = pk ∴ n > k .ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà76 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì...ÓòâåðæäåíèåÏóñòü β ∈ Fnp èìååò ïîðÿäîê l, à åãî ì.ì. m(x) èìååò ñòåïåíü k ...Òîãäà ¶ (pk − 1) .. l, à åñëè r < k , òî · (pr − 1) 6 .. l.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà76 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì...ÓòâåðæäåíèåÏóñòü β ∈ Fnp èìååò ïîðÿäîê l, à åãî ì.ì. m(x) èìååò ñòåïåíü k ...Òîãäà ¶ (pk − 1) ..
l, à åñëè r < k , òî · (pr − 1) 6 .. l.Äîêàçàòåëüñòâî¶ Ïî íåïðèâîäèìîìó ìíîãî÷ëåíó k -é ñòåïåíè m(x) ñòðîèìïîëå èç pk ýëåìåíòîâ. Âñå åãî íåíóëåâûå ýëåìåíòû, â òîìk÷èñëå è β , ÿâëÿþòñÿ êîðíÿìè óðàâíåíèÿ xp −1 − 1 = 0, ò.å.kkβ p −1 − 1 = 0 è β p −1 = 1, íî deg β = l ⇒ l | (pk − 1)..· Ïóñòü (pr − 1) .. l è r < k . Òîãäà β êîðåíü óðàâíåíèÿ.rrxp − 1 = 0, à ò.ê. m(x) ì.ì. äëÿ β , òî (xp − 1)..m(x) (áûëîräîêàçàíî) ⇒ íàéäåí íåïðèâîäèìûé äåëèòåëü xp − 1 ñòåïåíèk , íî k > r ⇒ ïðîòèâîðå÷èå äîêàçàííîìó ðàíåå.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà77 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì...Ñëåäóþùàÿ òåîðåìà ïîçâîëÿåò ðàñêëàäûâàòü ìíîãî÷ëåíû íàìíîæèòåëè.Òåîðåìà (ñâîéñòâî êîðíåé íåïðèâîäèìîãî ìíîãî÷ëåíà)Ïóñòü β êîðåíü íåïðèâîäèìîãî ìíîãî÷ëåíà f (x) ñòåïåíè n ñ2n−1êîýôôèöèåíòàìè èç Fp . Òîãäà ýëåìåíòû β, β p , β p , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
