1610841785-f468a61572dab6722e8deb8e3ec644ad (824277), страница 9
Текст из файла (страница 9)
Докажите два важных разложения над Zp (и запомните их):xp − ap = (x − a)p ,xp − x =Yk∈Zp(x − k).6. Докажите, что f (x)p = f (xp ) для любого многочлена f над Zp .Замечание. На самом деле, результаты двух предыдущих задач верны для любого поля характеристики p.Обозначим через Irr(Zp , d) множество унитарных (т. е.
со старшим коэффициентом 1) неприводимых многочленов степени d над Zp .Пример 2. Найдём а) Irr(Z2 , 2); б) Irr(Z3 , 2); в) Irr(Z3 , 4).а), б) Неприводимые многочлены степеней 2 и 3 — в точности многочлены, не имеющие корней.Многочлен x2 + ax + b не имеет корней в Z2 в точности при b 6= 0, 1 + a + b 6= 0 ⇔ a = b = 1, значит,Irr(Z2 , 2) = {x2 + x + 1}.Вообще, многочлен xn + . .
. + a0 не имеет корней в Z2 в точности тогда, когда a0 6= 0 и число мономовнечётно. В частности, Irr(Z3 , 2) = {x3 + x2 + 1, x3 + x + 1}.в) Если многочлен степени 4 не имеет корней, но приводим, то он равен произведению неприводимыхквадратных трёхчленов. В случае поля Z2 — квадрату трёхчлена x2 + x + 1, т. е. x4 + x2 + 1. Остальныемногочлены вида x4 + ax3 + bx2 + cx + 1, где среди a, b, c либо три единицы, либо ровно одна, неприводимынад Z2 .Ответ: а) x2 + x + 1; б) x3 + x2 + 1, x3 + x + 1; в) x4 + x3 + 1, x4 + x + 1, x4 + x3 + x2 + x + 1.7. Докажите, что многочлен x5 + x2 + 1 неприводим над а) Z2 ; б) Z.8.
Найдите Irr(Z3 , 2).9. Приведите пример многочлена из Irr(Z3 , 5).Для разложения многочленов над Zp на неприводимые проверяют наличие корней и делимостьна неприводимые многочлены степеней 2, 3, . . . Вообще, существуют алгоритмы разложения надZp . Ограничимся несколькими типовыми приёмами.Пример 3. Разложите многочлен x4 + x2 + 1 на неприводимые над а) Z2 ; б) Z3 .а) Над Z2 : x4 + x2 + 1 = (x2 + x + 1)2 и x2 + x + 1 неприводим (см. выше).б) y 2 + y + 1 имеет корень 1 в Z3 ; y 2 + y + 1 = (y − 1)2 , отсюда x4 + x2 + 1 = (x2 − 1)2 = (x − 1)2 (x + 1)2 .Пример 4.
Разложите многочлен x4 + 1 на неприводимые над Z3 , Z5 , Z7 , Z11 , Z17 .Корни есть только в Z17 (24 + 1 = 17): x4 + 1 = (x − 2)(x + 2) . . . = (x2 − 4)(x2 + 4); x2 + 4 = x2 − 64(64 + 4 = 17 · 4). Итак, x4 + 1 = (x − 2)(x + 2)(x − 8)(x + 8) в Z17 .Разложение, аналогичное x4 + 1 = (x2 − i)(x2 + i) в C, имеет место в тех полях, в которых естьэлемент с квадратом −1.
Из оставшихся — это только Z5 , где 22 = −1 и соответственно x4 + 1 = x4 − 4 =(x2 − 2)(x2 + 2).Двучлен x4 + 1 можно ещё двумя способами разложить на два квадратных трёхчлена в C: √√√√x4 + 1 = x2 − 2x + 1 x2 + 2x + 1 = x2 − i 2x − 1 x2 + i 2x − 1 .Соответственно, если в поле есть элемент с квадратом ±2, то имеет место одно из этих разложений:ZZZ11x4 + 1 =3 (x2 − x − 1)(x2 + x − 1), x4 + 1 =7 (x2 − 3x − 1)(x2 + 3x − 1), x4 + 1 =(x2 − 3x + 1)(x2 + 3x + 1).10. Разложите на неприводимые множители: а) x2 + 5x + 5 над Z11 ; б) x3 + 2 над Z3 ;в) x4 + x3 + x2 + x + 1 над Z5 ; г) x5 + x3 + x2 + 1 над Z2 ; д) x4 + x3 + x + 2 над Z3 ; е) x4 − 10x2 + 1над Z3 , Z7 , Z11 ; ж) x15 − 1 над Z11 .11∗.
Докажите, что неприводимые над Z многочлены а) x4 + 1; б) x4 − 10x2 + 1 приводимы надZp при любом простом p.Редукция многочленов по простому модулюРедуцируя коэффициентымногочлена f (x) =Pмногочлен [f (x)]p := k [ak ]p xk над полем Zp .Pkak xk ∈ Z[x] по модулю простого p, получим• Ясно, что [f ]p [g]p = [f g]p для всех f, g ∈ Z[x].
Поэтому если q | f в Z[x], то [q]p | [f ]p вZp [x]. Следовательно, если многочлен f приводим над Z, то многочлен [f ]p приводим надZp , коль скоро deg[f ]p = deg f . (Многочлен 2x2 + 3x + 1 приводим над Z, но многочлен[2x2 + 3x + 1]2 = x + 1 неприводим над Z2 .)• При редукции неприводимый многочлен может перейти в приводимый, у него могут появиться корни, некоторые из корней могут совпасть.
Примеры: x2 + x + 1 = x2 − 2x + 1 = (x − 1)2в Z3 [x], x2 + x + 1 = x2 + x − 6 = (x − 2)(x + 3) = −(2x − 1)(3x + 1) в Z7 [x].• Используя редукцию, можно коротко переформулировать доказательство леммы Гаусса.C Если многочлены f, g ∈ Z[x] примитивны, но все коэффициенты многочлена f g кратныпростому p, то [f g]p = [f ]p [g]p = 0.
Но [f ]p , [g]p 6= 0, а в кольце Zp [x] нет делителей нуля. B• Редукция также даёт короткое и концептуальное доказательство признака Эйзенштейна.C Если f = gh, g, h ∈ Z[x], deg g, deg h > 0, то [an xn ]p = [f ]p = [g]p [h]p , откуда [g]p и [h]pассоциированы со степенями [x]p (кольцо Zp [x] факториально). Это, в частности, означает,что их свободные члены кратны p, а тогда свободный член у f кратен p2 — противоречие. B• Пусть многочлен неприводим над Z.
Может ли он быть приводим при редукции по любомупростому модулю? Оказывается, да — см. задачу 11.Рациональные корни многочленов над Z при редукции. Доказать отсутствие рациональных корней у многочлена над Z часто удаётся с помощью редукции по подходящему модулю.Начнём с примеров.• Многочлен f (x) = x5 − 7x4 + 12x3 + 21x2 − 3x + 75 как при чётных, так и при нечётныхx принимает нечётные значения, а значит, не имеет целых корней.
(На языке редукции:многочлен [f (x)]2 = x5 + x4 + x2 + x + 1 не имеет корней в Z2 , а значит, f (x) не имеет корнейв Z.) В силу теоремы 1 многочлен f (x) не имеет и рациональных корней.• Аналогично многочлен f (x) = 35x5 − 11x4 + 2x3 − 3x2 + 5x − 99 не имеет корней в Z, т. к.многочлен [f (x)]2 не имеет корней в Z2 . Но почему f (x) не имеет корней в Q (в отличие отпредыдущего примера, здесь lc f > 1)? Если f (m/n) = 0 и (m, n) = 1, то по теореме 1 m | 99и n | 35, в частности, n обратимо в Z2 (на самом деле, m = n = 1 в Z2 ).
Значит, равенствоf (m/n) = 0 верно в Z2 — противоречие.• Многочлен g(x) = 20x4 +27x3 −13x2 −15x+28 имеет нулевой корень в Z2 , зато не имеет корнейв Z3 : [g(x)]3 = −x4 − x2 + 1. Отсюда следует, что g(x) не имеет корней в Q, т. к. его старшийкоэффициент 20 взаимно прост с 3, т. е. обратим в Z3 (а значит, всякий рациональный кореньбыл бы корнем в Z3 аналогично предыдущему примеру).• Подчеркнём, что при редукции многочлена по модулю p важно следить за обратимостью егостаршего коэффициента в Zp . Взять хоть бы многочлен 2x + 1, у которого отсутствие корнейв Z2 не влечёт их отсутствие в Q.Можно подытожить и обобщить сказанное:если f (x) = ak xk + .
. . ∈ Z[x], p — простое и p - ak , тоf (x) не имеет корней в Q ⇐⇒ f (x) не имеет корней в Zp .В частности, при p = 2, 3 получаем полезную теорему 2.12∗. Докажите с помощью редукции неприводимость многочленов над Z:а) x5 + x2 + 1; б) 7x4 − 2x2 + 3x + 8; в) x5 − 6x3 + 2x2 − 4x + 5; г) x4 − 4x3 + x2 + x − 4.Решение. а) Многочлен x5 + x2 + 1 неприводим над Z2 (а значит, и над Z), т.
к. он не имееткорней в Z2 и не делится на единственный неприводимый многочлен x2 + x + 1 второй степени:x5 ≡ x2 + x2 + 1 = 1 (mod x2 + x + 1), т. к. x2 + x + 1 | x3 − 1 и x5 ≡ x2 (mod x3 − 1).(x5 − 1 = (x − 1)(x4 + x3 + x2 + x + 1) (mod 2)532— разложения нав) x − 6x + 2x − 4x + 5 ≡x5 − x2 − x − 1 = (x2 + 1)(x3 − x − 1) (mod 3)неприводимые над Z2 и Z3 имеют разные наборы степеней, следовательно, многочлен неприводимнад Z (почему?).13∗. Неприводимость круговых многочленов над Z. Выше мы доказали неприводимостькруговых многочленов Φp при простых p. Докажем вместе с читателем, что круговой многочленΦn неприводим над Z при любом n ∈ N.
Это хороший пример применения редукции по простомумодулю.C Разложим двучлен xn − 1 на неприводимые над Z и обозначим через f (x) тот из неприводимых множителей, корнем которого является e2πi/n (для определённости). Пусть xn − 1 = f (x)g(x).Покажем, что f = Φn . Для этого достаточно показать, что для любого корня δ многочлена f илюбого простого p - n число δ p тоже является корнем многочлена f , т. к. 1 .Итак, пусть p — любое простое число, не делящее n. Тогда ([f ]p , [g]p ) = 1, т. к. 2 .
Поскольку3 , то f (x) | f (xp ) или f (x) | g(xp ). Но если f (x) | g(xp ), то ([f ]p , [g]p ) 6= 1: 4 . Значит, f (x) | f (xp ),откуда f (δ p ) = 0, причём δ p — первообразный корень из единицы n-й степени, т. к. p - n. BФормальное дифференцирование многочленовПроизводную f 0 (x) многочлена f (x) над полем K можно определить непосредственно:(a0 + a1 x + a2 x2 + . . . + an xn )0 = a1 + 2a2 x + .
. . + nan xn−1 .Полезно также дать эквивалентное определение, восходяшее к аналитическому (через предел):f (x + h) − f (x) 0⇐⇒ f (x + h) = f (x) + hf 0 (x) + h2 (. . .)f (x) =hh=0Свойства дифференцирования.(1) Линейность: (f + g)0 = f 0 + g 0 и (cf )0 = cf 0 для всех c ∈ K (очевидно).(2) Дифференцирование произведения: (f g)0 = f 0 g + f g 0 и, вообще, по индукции 0fn0f10+ ... +.(f1 . . . fn ) = (f1 .
. . fn )f1fn(4)(Ввиду линейности по f и по g достаточно проверить для мономов f (x) = xm , g(x) = xn , а это легко.)(3) Дифференцирование композиции: f (g(x))0 = f 0 (g(x))g 0 (x).(Ввиду линейности обеих частей по f , можно считать, что f (x) = xn . А тогда применяем (4) дляf1 = . . . = fn = g.)nPCnk f (k) g (n−k) .(4) Правило Лейбница: (f g)(n) =k=0k(Для n = 1 доказано. Далее по индукции10 с использованием тождества Cn+1= Cnk + Cnk−1 .)Теорема 1. Дифференцирование продолжается с кольца K[x] на его поле частных K(x) ссохранением указанных свойств, и притом однозначно.Отметим один важный частный случай формулы (4):11Π0 (x)=+ ... +.Π(x) = (x − x1 ) .
. . (x − xn ) =⇒Π(x)x − x1x − xnВот как можно записать интерполяционный многочлен f (x) с условиями deg f < n, f (xi ) = yi ,i = 1, . . . , n (x1 , . . . , xn различны):f (x) = Π(x)nXi=1Π0 (xyii )(x − xi )(5)Пример 1. Многочлен степени < n принимает значения y1 , . . . , yn в корнях n-й степени из единицы(в каком-то порядке). Найдём f (0).√Применим формулу (5) в случае {x1 , . .
. , xn } = n 1. Имеем Π(x) = xn − 1 и Π0 (x) = nxn−1 . Отсюдаnf (x) = (x − 1)nXi=1nyi1X=⇒f(0)=yi .nnxn−1(x − xi )ii=11. Докажите, что точки x1 , . . . , xn ∈ C являются вершинами правильного n-угольника с центромPв точке x0 в точности тогда, когда f (x0 ) = n1 ni=1 f (xi ) для любого многочлена f ∈ C[x] степени < n.2. Докажите, что по значениям многочлена f ∈ C[x] в вершинах правильного n-угольника восстанавливается значение производной f 0 в центре этого n-угольника: для всех a ∈ C и r > 0 верно равенствоf 0 (a) =n−12πik1 X − 2πik e n f a + re n .nrk=0Это дискретный аналог интегральной формулы Коши (см.
курс комплексного анализа).nPxki3. Многочлен f степени n имеет n различных корней x1 , . . . , xn . Найдитеf 0 (xi ) при k = 0, . . . , n − 1.i=1n = 2, 3 : (f g) = (f g + f g ) = f g + 2f g + f g ⇒ (f g) = f g + 3f g + 3f g + g 000 и т. д. Теперь понятенмеханизм появления биномиальных коэффициентов — как в треугольнике Паскаля при раскрытии бинома.100000 0000 000000000000 00Теорема 2 (формула Тейлора).
В случае char K = 0 для любого многочлена f ∈ K[x]степени n и любого элемента a ∈ K имеет место формула Тейлора:f (x) =nXf (k) (a)k=0k!(x − a)k = f (a) + f 0 (a)(x − a) +f 00 (a)f (n) (a)(x − a)2 + . . . +(x − a)n .2!n!(6)PC Разложим многочлен f (x) по степеням x − a: f (x) = nk=0 ck (x − a)k . Продифференцировавm раз и подставив в полученное равенство точку x = a, получим, что f (m) (a) = m!cm , m = 0, .
. . , n.Поскольку char K = 0, то m! 6= 0 в K при всех m, а потому можно делить на m!. BЗамечание. Подчеркнём, что любой многочлен f (x) над любым полем можно разложить по степенямлюбого двучлена x − a (независимо от характеристики): f (x) = g(x − a) для g(x) := f (x + a), причёмкоэффициенты разложения быстро ищутся по схеме Горнера. Условие на характеристику существеннодля выражения коэффициентов разложения через производные. Над полями характеристики p формулаТейлора верна только для многочленов степени < p.Следствия. Пусть char K = 0 и f ∈ K[x].(1) Если a — корень кратности n многочлена f , то a — корень кратности n − 1 многочленаf 0 (если n = 1, то f 0 (a) 6= 0).(2) Если f (a) = 0, то a — корень кратности n многочлена f в точности тогда, когда f (a) =0f (a) = .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
