PA_full (1127144), страница 6
Текст из файла (страница 6)
+ cnn= 0.Таким образом, � корень многочленаf (x) = c0 + c1 x + . . . + cn xn .Минимальным многочленом для будет некоторыйнормированный неприводимый делитель f (x).Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем62 / 432Многочлены над конечным полем: свойстваТеоремаЛюбой ненулевой элемент поляnмногочлена xp 1 1, т.е.xpгде1,...,n1pn 11 = (x=n⇤p=npявляется корнем1 ) · .
. . · (xn r {0}.ppn 1 ),Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем62 / 432Многочлены над конечным полем: свойстваТеоремаЛюбой ненулевой элемент поляnмногочлена xp 1 1, т.е.xpгде1,...,n1pn 11 = (x=n⇤p=npявляется корнем1 ) · . . . · (xn r {0}.ppn 1 ),Доказательствоn⇤ � циклическая группа по умножению порядка pn1.pПорядок deg ↵ любого элемента ↵ 2 n⇤(т.е.порядокpциклической подгруппы h↵i) по теореме Лагранжа делитпорядок группы.Поэтому pn 1 = q · deg ↵, ↵deg ↵ = 1 и↵pn11 = ↵q deg ↵1 = (↵deg ↵ )q1 = 1q1 = 0.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем: свойства...СледствиеВсе элементы поля np , не исключая нуля, являются корнямиnмногочлена xpx.63 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем63 / 432Многочлены над конечным полем: свойства...СледствиеВсе элементы поля np , не исключая нуля, являются корнямиnмногочлена xpx.ДоказательствоВынесем x за скобку:xpnx = x xpn11 .У второго сомножителя корнями будут все ненулевыеэлементы, а у первого � 0.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем: свойства...Теорема.(xn 1) ..
(xm.1) , n .. m.64 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем: свойства...Теорема.(xn 1) .. (xm.1) , n .. m.ДоказательствоПусть n = mk. Сделаем замену: xm = y, тогдаxn 1 = y k 1 и xm 1 = y 1. Делимость очевидна,поскольку 1 является корнем y k 1.64 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем64 / 432Многочлены над конечным полем: свойства...Теорема.(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, тогдаxn1 =xr (xmk 1)(xm 1)+ xr 1 =xm 1xr (xmk 1) m=(x1) + xrxm 11.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем: свойства...Последнее выражение задает результат деления xn 1 наxm 1 с остатком, поскольку xmk 1 делится на xm 1 подоказанному выше.Остаток xr 1 6= 0 в силу сделанных предположений.) xn 1 не делится на xm 1.65 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем65 / 432Многочлены над конечным полем: свойства...Последнее выражение задает результат деления xn 1 наxm 1 с остатком, поскольку xmk 1 делится на xm 1 подоказанному выше.Остаток xr 1 6= 0 в силу сделанных предположений.) xn 1 не делится на xm 1.Теорема даёт возможность раскладывать многочлены xnпри составных n.Например, разложим x15 + 1 в поле характеристики 2(где 1 = +1):x15 + 1 = (x3 + 1)(x12 + x9 + x6 + x3 + 1),(3 | 15).Продолжить это разложение помогает следующая теорема.1Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем66 / 432Многочлены над конечным полем...ТеоремаВсе неприводимые многочлены n-й степени изnделителями xpx.p [x]являютсяПрикладная алгебраПоля ГалуаКорни многочленов над конечным полем66 / 432Многочлены над конечным полем...ТеоремаВсе неприводимые многочлены n-й степени изnделителями xpx.p [x]являютсяДоказательствоn = 1.
Убеждаемся, что (x a) | (xp x), где a 2 p : при a = 0это очевидно, а в остальных случаях доказано, что a �корень многочлена xp 1 1 = (xp x)/x.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем66 / 432Многочлены над конечным полем...ТеоремаВсе неприводимые многочлены n-й степени изnделителями xpx.p [x]являютсяДоказательствоn = 1. Убеждаемся, что (x a) | (xp x), где a 2 p : при a = 0это очевидно, а в остальных случаях доказано, что a �корень многочлена xp 1 1 = (xp x)/x.n > 1. Строим по неприводимому и (без ограничения общности �нормированному) многочлену f (x) степени n поле np .nВ этом поле x � корень и f (x), и xp 1 1, причёмf (x) � м.м. для него.nПо свойствам м.м.
xp 1 1 делится на f (x).Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем67 / 432Многочлены над конечным полем...Используя доказанную теорему, завершим разложениеx15 + 1 = (x3 + 1)(x12 + x9 + x6 + x3 + 1)на неприводимые над2многочлены.(⇤)Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем67 / 432Многочлены над конечным полем...Используя доказанную теорему, завершим разложениеx15 + 1 = (x3 + 1)(x12 + x9 + x6 + x3 + 1)на неприводимые над1x(x15x162(⇤)многочлены.4+ 1) =+ x = x2 + x, откуда все неприводимыемногочлены 4-й степени будут делителями x16 + x и,следовательно, x15 + 1.
Таких многочленов 3: x4 + x + 1,x4 + x3 + 1 и x4 + x3 + x2 + x + 1, и их произведение даствторой сомножитель в (⇤).Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем67 / 432Многочлены над конечным полем...Используя доказанную теорему, завершим разложениеx15 + 1 = (x3 + 1)(x12 + x9 + x6 + x3 + 1)на неприводимые над2(⇤)многочлены.41x(x15x16+ 1) =+ x = x2 + x, откуда все неприводимыемногочлены 4-й степени будут делителями x16 + x и,следовательно, x15 + 1.
Таких многочленов 3: x4 + x + 1,x4 + x3 + 1 и x4 + x3 + x2 + x + 1, и их произведение даствторой сомножитель в (⇤).2x(x3 + 1) = x4 + x = x2 + x, откуда все неприводимыемногочлены 2-й степени будут делителями x4 + x и,следовательно, x3 + 1. Такой многочлен только один:x2 + x + 1 и x3 + 1 = (x + 1)(x2 + x + 1).2В итоге получимx15 +1 = (x+1)(x4 +x+1)(x4 +x3 +1)(x4 +x3 +x2 +x+1)(x2 +x+1).Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем68 / 432Многочлены над конечным полем...ТеоремаЛюбой неприводимый делитель многочлена xpстепень, не превосходящую n.n11 имеетПрикладная алгебраПоля ГалуаКорни многочленов над конечным полем68 / 432Многочлены над конечным полем...ТеоремаЛюбой неприводимый делитель многочлена xpстепень, не превосходящую n.n11 имеетДоказательствоnПусть ' � неприводимый делитель xpx степени k.defТогда F = p /(') � поле, котороеn рассмотрим oкак векторноепространство надpс базисом1, x, .
. . , xk1.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем69 / 432Многочлены над конечным полем...Обозначим x = ↵. Поскольку (xpn↵p↵ = 0.n.x) ..', то в F имеемЛюбой элемент F выражается через базис:=kP1ai ↵ i .i=0Возведя обе части этого равенства в степень pn , получим✓k 1◆p nkP1Ppn =iai ↵=ai ↵ i = ,i=0т.е.i=0� корень уравненияxpnx = 0.(⇤)Итак, каждый элемент поля F является корнем (⇤), но у (⇤) неболее pn различных корней, а |F | = pk .) n > k.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем...УтверждениеПустьnpимеет порядок l, а его м.м.
m(x) имеет степень k...Тогда (a) (pk 1) .. l, а если r < k, то (b) (pr 1) 6 .. l.270 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем...УтверждениеПустьnpимеет порядок l, а его м.м. m(x) имеет степень k...Тогда (a) (pk 1) .. l, а если r < k, то (b) (pr 1) 6 .. l.2Доказательство(a) По неприводимому многочлену k-й степени m(x) строимполе из pk элементов. Все его ненулевые элементы, в том числеkи , являются корнями уравнения xp 1 1 = 0, т.е.kpk 11 = 0 и p 1 = 1, но deg = l ) l | (pk 1)..(b) Пусть (pr 1) .. l и r < k.
Тогда � корень уравнения.rrxp1 = 0, а т.к. m(x) � м.м. для , то (xp1)..m(x) (былодоказано). Мы нашли неприводимый делитель многочленаrxp1 степени k, но k > r, что противоречит доказанномуранее.70 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем...Следующая теорема нужна для того, чтобы раскладыватьмногочлены на множители.ТеоремаПусть 2 np � корень неприводимого многочлена '(x)n 1степени n с коэффициентами из p . Тогда , p , . . .
, p :12все различны;исчерпывают список корней '(x).Т.е. чтобы получить все корни неприводимого многочлена,достаточно найти один из них и возводить его последовательнов степень p.71 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем71 / 432Многочлены над конечным полем...Следующая теорема нужна для того, чтобы раскладыватьмногочлены на множители.ТеоремаПусть 2 np � корень неприводимого многочлена '(x)n 1степени n с коэффициентами из p . Тогда , p , . .
. , p :12все различны;исчерпывают список корней '(x).Т.е. чтобы получить все корни неприводимого многочлена,достаточно найти один из них и возводить его последовательнов степень p.Доказательство(1) Покажем, что если� корень '(x), тоp� тоже корень.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем72 / 432Многочлены над конечным полем...Поскольку ap = a для всех a 2a0 + a1 x + . . . + a k xkpp,то справедливо= ap0 + ap1 xp + ap2 x2p + . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
