Лекции по прикладной алгебре. v1.0 (1127110), страница 2
Текст из файла (страница 2)
. .Ñâîéñòâà:ϕ(n) > n − 1 è ϕ(p) = p − 1, åñëè p ïðîñòîå;ϕ(nm ) = nm−1 ϕ(n − 1), ò.å. ϕ(pm ) = pm−1 (p − 1), åñëèp ïðîñòîå;åñëè m è n âçàèìíî ïðîñòû, òî ϕ(m · n) = ϕ(m) · ϕ(n) (ò.å.ϕ(n) ìóëüòïëèêàòèâíàÿ ôóíêöèÿ);d, ãäå d = (m, n).â îáùåì ñëó÷àå ϕ(m·n) = ϕ(m)·ϕ(n)· ϕ(d)Ïðèìåðϕ(15) =Ïðèêëàäíàÿ àëãåáðà13 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÔóíêöèÿ Ýéëåðàϕ(n) ôóíêöèÿ Ýéëåðà ò.å. êîëè÷åñòâî ÷èñåë ðÿäà èçèíòåðâàëà [ 1, . . . , n − 1 ], âçàèìíî ïðîñòûõ ñ n:ϕ(1) = 1 (ïî îïðåäåëåíèþ), ϕ(2) = 1, ϕ(3) = ϕ(4) = 2,ϕ(5) = 4, ϕ(6) = |{1, 5}| = 2, . . .Ñâîéñòâà:ϕ(n) > n − 1 è ϕ(p) = p − 1, åñëè p ïðîñòîå;ϕ(nm ) = nm−1 ϕ(n − 1), ò.å. ϕ(pm ) = pm−1 (p − 1), åñëèp ïðîñòîå;åñëè m è n âçàèìíî ïðîñòû, òî ϕ(m · n) = ϕ(m) · ϕ(n) (ò.å.ϕ(n) ìóëüòïëèêàòèâíàÿ ôóíêöèÿ);d, ãäå d = (m, n).â îáùåì ñëó÷àå ϕ(m·n) = ϕ(m)·ϕ(n)· ϕ(d)Ïðèìåðϕ(15) = ϕ(3 · 5) = ϕ(3) · ϕ(5) = (3 − 1)(5 − 1) = 8.Ïðèêëàäíàÿ àëãåáðà14 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÊàê íàéòè ïðèìèòèâíûå ýëåìåíòû ïîëÿFp ?Ïðèêëàäíàÿ àëãåáðà14 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÊàê íàéòè ïðèìèòèâíûå ýëåìåíòû ïîëÿÅñëè ïðèìàðíîå ðàçëîæåíèå (p − 1) Fp ?Ïðèêëàäíàÿ àëãåáðà14 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÊàê íàéòè ïðèìèòèâíûå ýëåìåíòû ïîëÿFp ?Åñëè ïðèìàðíîå ðàçëîæåíèå (p − 1) èçâåñòíî ýëåìåíò α ∈ Fp áóäåò ïðèìèòèâíûì iαp−1q6≡p 1 äëÿ êàæäîãî ïðîñòîãî q | (p − 1).Ïðèêëàäíàÿ àëãåáðà14 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÊàê íàéòè ïðèìèòèâíûå ýëåìåíòû ïîëÿFp ?Åñëè ïðèìàðíîå ðàçëîæåíèå (p − 1) èçâåñòíî ýëåìåíò α ∈ Fp áóäåò ïðèìèòèâíûì ip−1α q 6≡p 1 äëÿ êàæäîãî ïðîñòîãî q | (p − 1).íåèçâåñòíî ýôôåêòèâíîãî àëãîðèòìà íàõîæäåíèÿ ïðèìèòèâíîãîýëåìåíòà íå íàéäåíî (èñïîëüçóþò âåðîÿòíîñòíûåàëãîðèòìû).Ïðèêëàäíàÿ àëãåáðà14 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÊàê íàéòè ïðèìèòèâíûå ýëåìåíòû ïîëÿFp ?Åñëè ïðèìàðíîå ðàçëîæåíèå (p − 1) èçâåñòíî ýëåìåíò α ∈ Fp áóäåò ïðèìèòèâíûì ip−1α q 6≡p 1 äëÿ êàæäîãî ïðîñòîãî q | (p − 1).íåèçâåñòíî ýôôåêòèâíîãî àëãîðèòìà íàõîæäåíèÿ ïðèìèòèâíîãîýëåìåíòà íå íàéäåíî (èñïîëüçóþò âåðîÿòíîñòíûåàëãîðèòìû).Åñëè íàéäåí îäèí ïðèìèòèâíûé ýëåìåíò, îñòàëüíûå íàõîäÿòñÿâîçâåäåíèåì åãî â ñòåïåíè, âçàèìíî ïðîñòûå ñ ÷èñëîì p − 1 .Ïðèêëàäíàÿ àëãåáðà15 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÍåïðèâîäèìûå ìíîãî÷ëåíûÓòâåðæäåíèåÊîëüöî ìíîãî÷ëåíîâ k[x] íàä ïîëåì k åâêëèäîâî.ÒåîðåìàÊàæäûé ýëåìåíò åâêëèäîâà êîëüöà îäíîçíà÷íî ñ òî÷íîñòüþ äîïåðåñòàíîâîê ðàçëàãàåòñÿ â ïðîèçâåäåíèå ïðîñòûõ ýëåìåíòîâ.
èäåëèòåëåé åäèíèöû.Ïðîñòûå (íåðàçëîæèìûå) ýëåìåíòû k[x] íåïðèâîäèìûåìíîãî÷ëåíû.Âîïðîñû äëÿ ïîëåé C, R,12Q è Fp :êàêèå ìíîãî÷ëåíû íàä íèìè íåïðèâîäèìû?êàê íàõîäèòü íåïðèâîäèìûå ìíîãî÷ëåíû?Ïðèêëàäíàÿ àëãåáðàÏîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÑâîéñòâà êîðíåé ìíîãî÷ëåíîâÓòâåðæäåíèåÎñòàòîê îò äåëåíèÿ ìíîãî÷ëåíà f íà ìíîãî÷ëåí ïåðâîé ñòåïåíè(x−a) ðàâåí f (a).  ÷àñòíîñòè, f äåëèòñÿ íà (x−a) i a ÿâëÿåòñÿêîðíåì f , ò. å. f (a) = 0.16 / 225Ïðèêëàäíàÿ àëãåáðàÏîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÑâîéñòâà êîðíåé ìíîãî÷ëåíîâÓòâåðæäåíèåÎñòàòîê îò äåëåíèÿ ìíîãî÷ëåíà f íà ìíîãî÷ëåí ïåðâîé ñòåïåíè(x−a) ðàâåí f (a).  ÷àñòíîñòè, f äåëèòñÿ íà (x−a) i a ÿâëÿåòñÿêîðíåì f , ò. å. f (a) = 0.ÄîêàçàòåëüñòâîÐàçäåëèì f ñ îñòàòêîì íà x − a. Îñòàòîê äîëæåí èìåòü ñòåïåíü0, ò.å.
f (x) = q · (x − a) + b, îòêóäà f (a) = b.16 / 225Ïðèêëàäíàÿ àëãåáðà17 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÎñíîâíàÿ òåîðåìà àëãåáðûËåììàÌíîãî÷ëåí ñòåïåíè n èìååò íå áîëåå n êîðíåé. Åñëè äâàìíîãî÷ëåíà ñòåïåíè íå âûøå n êàê ôóíêöèè ðàçëè÷íû, òî èõçíà÷åíèÿ ñîâïàäàþò íå áîëåå ÷åì â n òî÷êàõ.⇒ Óêàçàííûå ìíîãî÷ëåíû ¾ñèëüíî îòëè÷àþòñÿ îäèí îòäðóãîãî¿.Ýòî ñâîéñòâî ìíîãî÷ëåíîâ ëåæèò â îñíîâå ìíîãèõ èõïðèìåíåíèé â êîìáèíàòîðèêå è â òåîðåòè÷åñêîé èíôîðìàòèêå.Òåîðåìà (îñíîâíàÿ òåîðåìà àëãåáðû)Âñÿêèé ìíîãî÷ëåí ïîëîæèòåëüíîé ñòåïåíè íàä ïîëåìêîðåíü.CèìååòÏðèêëàäíàÿ àëãåáðà18 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÍåïðèâîäèìûå ìíîãî÷ëåíû íàä C,Íåïðèâîäèìûå ìíîãî÷ëåíû:RèQÏðèêëàäíàÿ àëãåáðà18 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÍåïðèâîäèìûå ìíîãî÷ëåíû íàä C,RèQÍåïðèâîäèìûå ìíîãî÷ëåíû:â ïîëåC òîëüêî ìíîãî÷ëåíû 1-é ñòåïåíè;Ïðèêëàäíàÿ àëãåáðà18 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÍåïðèâîäèìûå ìíîãî÷ëåíû íàä C,RèQÍåïðèâîäèìûå ìíîãî÷ëåíû:â ïîëåâ ïîëåCR òîëüêî ìíîãî÷ëåíû 1-é ñòåïåíè;1 ìíîãî÷ëåíû 1-é ñòåïåíè,2 ìíîãî÷ëåíû 2-é ñòåïåíè ñ îòðèöàòåëüíûìäèñêðèìèíàíòîì;Ïðèêëàäíàÿ àëãåáðà18 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÍåïðèâîäèìûå ìíîãî÷ëåíû íàä C,RèQÍåïðèâîäèìûå ìíîãî÷ëåíû:â ïîëåâ ïîëåCRâ ïîëåQ òîëüêî ìíîãî÷ëåíû 1-é ñòåïåíè;1 ìíîãî÷ëåíû 1-é ñòåïåíè,2 ìíîãî÷ëåíû 2-é ñòåïåíè ñ îòðèöàòåëüíûìäèñêðèìèíàíòîì; ñóùåñòâóþò íåïðèâîäèìûå ìíîãî÷ëåíûïðîèçâîëüíîé ñòåïåíè (íàäî ïîêàçàòü).Âîïðîñ î ïðèâîäèìîñòè ìíîãî÷ëåíà ñâîäèòñÿ ê âîïðîñóî ðàçëîæåíèè íà ìíîæèòåëè ìíîãî÷ëåíà ñ öåëûìèêîýôôèöèåíòàìè.Ïðèêëàäíàÿ àëãåáðàÏîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÊðèòåðèé Ýéçåíøòåéíà äîñòàòî÷íîå óñëîâèåíåïðèâîäèìîñòè ìíîãî÷ëåíîâ íàä QÒåîðåìà (êðèòåðèé Ýéçåíøòåéíà)Åñëè äëÿ ìíîãî÷ëåíà an xn + .
. . + a1 x + a0 ñ öåëûìèêîýôôèöèåíòàìè ñóùåñòâóåò òàêîå ïðîñòîå p, ÷òî (1) p - an ,p | ai ïðè i = 0, 1, . . . , n − 1 è (2) p2 - a0 , òî ýòîò ìíîãî÷ëåííåïðèâîäèì.19 / 225Ïðèêëàäíàÿ àëãåáðàÏîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÊðèòåðèé Ýéçåíøòåéíà äîñòàòî÷íîå óñëîâèåíåïðèâîäèìîñòè ìíîãî÷ëåíîâ íàä QÒåîðåìà (êðèòåðèé Ýéçåíøòåéíà)Åñëè äëÿ ìíîãî÷ëåíà an xn + . . . + a1 x + a0 ñ öåëûìèêîýôôèöèåíòàìè ñóùåñòâóåò òàêîå ïðîñòîå p, ÷òî (1) p - an ,p | ai ïðè i = 0, 1, . .
. , n − 1 è (2) p2 - a0 , òî ýòîò ìíîãî÷ëåííåïðèâîäèì.Ïðèìåð2x4 − 6x3 + 15x2 + 21 íåïðèâîäèì ïî êðèòåðèþ Ýéçåíøòåéíà(p = 3).19 / 225Ïðèêëàäíàÿ àëãåáðà19 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÊðèòåðèé Ýéçåíøòåéíà äîñòàòî÷íîå óñëîâèåíåïðèâîäèìîñòè ìíîãî÷ëåíîâ íàä QÒåîðåìà (êðèòåðèé Ýéçåíøòåéíà)Åñëè äëÿ ìíîãî÷ëåíà an xn + . . .
+ a1 x + a0 ñ öåëûìèêîýôôèöèåíòàìè ñóùåñòâóåò òàêîå ïðîñòîå p, ÷òî (1) p - an ,p | ai ïðè i = 0, 1, . . . , n − 1 è (2) p2 - a0 , òî ýòîò ìíîãî÷ëåííåïðèâîäèì.Ïðèìåð2x4 − 6x3 + 15x2 + 21 íåïðèâîäèì ïî êðèòåðèþ Ýéçåíøòåéíà(p = 3).Ïðèìåð(ñóùåñòâîâàíèåíàäìíîãî÷ëåíîâ ëþáîé ñòåïåíè)QíåïðèâîäèìûõÌíîãî÷ëåí xn − 2 äëÿ âñÿêîãî n > 0 íåïðèâîäèì íàäêðèòåðèþ Ýéçåíøòåéíà äëÿ p = 2.QïîÏðèêëàäíàÿ àëãåáðà20 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÍåïðèâîäèìûå ìíîãî÷ëåíû íàäñëó÷àéÏðèìåð (p = 2)Fp îñíîâíîé äëÿ íàñÄàíî: ïîëå F2 = h{0, 1}, +mod 2 , ·mod 2 i.Òðåáóåòñÿ: íàéòè âñå íåïðèâîäèìûå ìíîãî÷ëåíû ñòåïåíåé 2, 3,4 íàä íèì.Ïðèêëàäíàÿ àëãåáðà20 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÍåïðèâîäèìûå ìíîãî÷ëåíû íàäñëó÷àéFp îñíîâíîé äëÿ íàñÏðèìåð (p = 2)Äàíî: ïîëå F2 = h{0, 1}, +mod 2 , ·mod 2 i.Òðåáóåòñÿ: íàéòè âñå íåïðèâîäèìûå ìíîãî÷ëåíû ñòåïåíåé 2, 3,4 íàä íèì.Âòîðàÿ ñòåïåíü: x2 + ax + bßñíî, ÷òî b = 1, èíà÷å x2 + ax = x(x + a).Èùåì íåïðèâîäèìûé ìíîãî÷ëåí â âèäå x2 + ax + 1.Ïðèêëàäíàÿ àëãåáðà20 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÍåïðèâîäèìûå ìíîãî÷ëåíû íàäñëó÷àéFp îñíîâíîé äëÿ íàñÏðèìåð (p = 2)Äàíî: ïîëå F2 = h{0, 1}, +mod 2 , ·mod 2 i.Òðåáóåòñÿ: íàéòè âñå íåïðèâîäèìûå ìíîãî÷ëåíû ñòåïåíåé 2, 3,4 íàä íèì.Âòîðàÿ ñòåïåíü: x2 + ax + bßñíî, ÷òî b = 1, èíà÷å x2 + ax = x(x + a).Èùåì íåïðèâîäèìûé ìíîãî÷ëåí â âèäå x2 + ax + 1.
Òàêèõìíîãî÷ëåíîâ âñåãî äâà: x è x + 1, à äåëèìîñòü íà ïåðâûé ìûóæå èñêëþ÷èëè, òî îñòàëîñü èñêëþ÷èòü äåëèìîñòü íà x + 1.Äåëàåì çàìåíó y = x + 1 (x = y + 1): (y + 1)2 + a(y + 1) + 1 =y 2 + ay + (1 + a + 1), ñâîáîäíûé ÷ëåí äîëæåí áûòü 6= 0.Ïðèêëàäíàÿ àëãåáðà20 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÍåïðèâîäèìûå ìíîãî÷ëåíû íàäñëó÷àéFp îñíîâíîé äëÿ íàñÏðèìåð (p = 2)Äàíî: ïîëå F2 = h{0, 1}, +mod 2 , ·mod 2 i.Òðåáóåòñÿ: íàéòè âñå íåïðèâîäèìûå ìíîãî÷ëåíû ñòåïåíåé 2, 3,4 íàä íèì.Âòîðàÿ ñòåïåíü: x2 + ax + bßñíî, ÷òî b = 1, èíà÷å x2 + ax = x(x + a).Èùåì íåïðèâîäèìûé ìíîãî÷ëåí â âèäå x2 + ax + 1.
Òàêèõìíîãî÷ëåíîâ âñåãî äâà: x è x + 1, à äåëèìîñòü íà ïåðâûé ìûóæå èñêëþ÷èëè, òî îñòàëîñü èñêëþ÷èòü äåëèìîñòü íà x + 1.Äåëàåì çàìåíó y = x + 1 (x = y + 1): (y + 1)2 + a(y + 1) + 1 =y 2 + ay + (1 + a + 1), ñâîáîäíûé ÷ëåí äîëæåí áûòü 6= 0.∴ íàä F2 ñóùåñòâóåò åäèíñòâåííûé íåïðèâîäèìûé ìíîãî÷ëåíñòåïåíè 2 x2 + x + 1.Ïðèêëàäíàÿ àëãåáðà21 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÍåïðèâîäèìûå ìíîãî÷ëåíû íàäFp ...Òðåòüÿ ñòåïåíü: x3 + ax2 + bx + 1 (ïî÷åìó ñâîáîäíûé ÷ëåí íåðàâåí íóëþ?)Èñêëþ÷àåì (êàê ñäåëàíî ðàíåå) äåëèìîñòü íà x + 1 ïîëó÷àåìóñëîâèå a + b 6= 0, ò.å.a = 0, b = 1 ,a = 1, b = 0 .Ïðèêëàäíàÿ àëãåáðà21 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÍåïðèâîäèìûå ìíîãî÷ëåíû íàäFp ...Òðåòüÿ ñòåïåíü: x3 + ax2 + bx + 1 (ïî÷åìó ñâîáîäíûé ÷ëåí íåðàâåí íóëþ?)Èñêëþ÷àåì (êàê ñäåëàíî ðàíåå) äåëèìîñòü íà x + 1 ïîëó÷àåìóñëîâèå a + b 6= 0, ò.å.a = 0, b = 1 ,a = 1, b = 0 .∴ íàä F2 ñóùåñòâóåò äâà íåïðèâîäèìûõ ìíîãî÷ëåíà ñòåïåíè 3 x3 + x2 + 1 ,x3 + x + 1 .Ïðèêëàäíàÿ àëãåáðà22 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÍåïðèâîäèìûå ìíîãî÷ëåíû íàäFp ...×åòâ¼ðòàÿ ñòåïåíü: x4 + ax3 + bx2 + cx + 1Èñêëþ÷åíèå äåëèìîñòè íà x + 1 ïðèâîäèò ê óñëîâèþ a + b + c = 1,ò.å.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
