Ю.И. Журавлёв, Ю.А. Флёров, М.Н. Вялый - Дискретный анализ. Основы высшей алгебры (1127101), страница 23
Текст из файла (страница 23)
Эта лемма показывает, что многочлены «сильно отличаются один от другого». Именно это свойство многочленовлежит в основе многих их применений в комбинаторике и втеоретической информатике.Можно также заметить, что корни в лемме 3.7 могут быть икратными (по определению, a — корень кратности k означает,что f делится на (x − a)k и не делится на (x − a)k+1 ).Теперь посмотрим, какие многочлены неприводимы над полем комплексных чисел C.Теорема 3.9 (основная теорема алгебры). Всякий многочлен положительной степени над полем C имеет корень.Хотя эта теорема и называется основной теоремой алгебры, доказывать ее мы не будем, поскольку ее доказательствоотносится скорее к анализу, чем к алгебре.
(Простое доказательство основной теоремы алгебры см., например, в [5].)Из теоремы 3.9 и утверждения 3.6 вытекает, что над полемC неприводимы только многочлены первой степени. (Многочлен первой степени неприводим над любым полем, так какпри умножении многочленов их степени складываются, а многочлены нулевой степени обратимы.)Следующий пример — поле действительных чисел R. Чтобы перейти от поля C к полю R, заметим, что отображениеz 7→ z̄, сопоставляющее каждому комплексному числу z сопряженное число z̄, является изоморфизмом поля C на себя(автоморфизмом) и переводит поле R в себя. Отсюда вытекает,что для всякого p ∈ C[x] и всякого α ∈ C имеет место формула:p(α) = p̄(ᾱ),(3.2)134Глава 3.Конечные поля или поля Галуагде p̄ получается из p комплексным сопряжением коэффициентов.
Пусть теперь p ∈ R[x] ⊂ C[x] — многочлен степени > 1,не имеющий действительных корней (при наличии действительных корней p приводим). Многочлен p имеет комплексныйкорень α. Так как p = p̄, то из формулы (3.2) получаем, чтоp(ᾱ) = p̄(ᾱ) = p(α) = 0̄ = 0. Из утверждения 3.6 получаем, чтовзаимно простые многочлены x − α и x − ᾱ делят p. Но тогдаp делится и на их произведение q = (x − α)(x − ᾱ), котороепринадлежит R[x].Следовательно, над полем R неприводимы:а) многочлены первой степени;б) те многочлены второй степени, которые не имеют корнейв R (многочлены с отрицательным дискриминантом).Все прочие многочлены над R приводимы.Гораздо сложнее обстоит дело с многочленами над полемрациональных чисел Q.
Мы ограничимся лишь тем, что докажем существование неприводимых над Q многочленов произвольной степени.Если q — ненулевой многочлен с рациональными коэффициентами степени n, то, приводя коэффициенты к общемузнаменателю, можно записать: q = α(a0 + a1 x + · · · + an xn ) == αq0 , где все коэффициенты ai — целые числа, не имеющиенетривиального общего делителя, an > 0, α ∈ Q. Легко видеть,что многочлен q0 и число α определены однозначно. Будемназывать q0 примитивным многочленом, соответствующиммногочлену q.Лемма 3.10 (Гаусс). (uv)0 = u0 v0 .Доказательство. В сущности, нужно доказать, что если укаждого из многочленов u0 , v0 ∈ Z[x] коэффициенты взаимнопросты в совокупности, то у их произведения u0 v0 коэффициенты так же взаимно просты в совокупности.
Для доказательства построим гомоморфизм кольца Z[x] на кольцо GF (p)[x],который называется редукцией многочлена по модулю p. Редукция fp многочлена f получается приведением по модулюp каждого из коэффициентов f . Посмотрев на формулы длясуммы и произведения многочленов, видим, что редукция действительно является гомоморфизмом.3.3.Неприводимые многочлены135Предположим, что у коэффициентов u0 v0 есть общий простой делитель p. Тогда (u0 v0 )p и для редукций по модулю pимеем (u0 )p (v0 )p = 0. Поскольку в кольце GF (p)[x] нет делителей нуля (лемма 2.11), то одна из редукций (u0 )p , (v0 )pравна 0.
Это противоречит примитивности u0 , v0 .Таким образом, вопрос о приводимости многочлена над полем рациональных чисел сводится к вопросу о разложении намножители меньшей степени многочлена с целыми коэффициентами. В этом направлении имеется следующее достаточноеусловие неприводимости:Теорема 3.11 (критерий Эйзенштейна).
Если для многочлена q = a0 + a1 x + · · · + an xn с целыми коэффициентамисуществует такое простое число p, что p ∤ an , p | ai приi = 0, . . . , n − 1, p2 ∤ a0 , то этот многочлен неприводим.Доказательство. Предположим, что q приводимый многочлен: q = uv. Тогда qp = up vp . По условию теоремы qp = axn ,a 6= 0. Значит, up = bxk , vp = cxm , где k < n и m < n. Поэтомувсе коэффициенты многочленов u и v, кроме старших, делятсяна p, а тогда свободный член многочлена q, (т.
е. a0 ), равныйu0 v0 , делится на p2 , что противоречит условию.Пример 3.12. Многочлен 2x4 − 6x3 + 15x2 + 21 неприводимнад полем Q. Достаточно взять p = 3 и применить критерийЭйзенштейна.Пример 3.13. Для всякого n > 0 многочлен xn − 2 неприводим над Q. Достаточно взять p = 2 и применить критерийЭйзенштейна. Отсюда вытекает, что над полем рациональныхчисел существуют неприводимые многочлены любой степени.Теперь перейдем к самому важному для нас случаю многочленов над полем GF (p).
Начнем с примеров.Пример 3.14. Найдем все неприводимые многочлены степеней 2, 3, 4 над полем GF (2). В этом поле есть два элемента 0и 1, операции — сложение и умножение по модулю 2.Вторая степень: x2 + ax + b. Ясно, что b 6= 0, так как впротивном случае имеется разложение на нетривиальные делители x2 + ax = x(x + a). Значит, неприводимый многочлен136Глава 3.Конечные поля или поля Галуастепени 2 имеет вид x2 + ax + 1. Поскольку многочленов первой степени всего два: x и x + 1, а делимость на первый мыуже исключили, то осталось исключить делимость на x + 1.Это делается аналогично предыдущему случаю: после заменыy = x+1 остается проверить, что свободный член в разложениипо степеням y не равен 0.
Этот свободный член равен значению многочлена при x = 1 (в нашем поле −1 = 1). Поэтомуполучаем условие 1 + a + 1 6= 0, т. е. a 6= 0.Итак, неприводимый многочлен степени 2 единственный:x2 + x + 1.Третья степень: x3 + ax2 + bx + 1 (свободный член не равеннулю, иначе имеем делитель x).Исключим делимость на x + 1, получаем условие a + b 6= 0.Т. е. имеем два решения a = 0, b = 1 и a = 1, b = 0.Соответственно, имеем два неприводимых многочлена степени 3:x3 + x2 + 1,x3 + x + 1.Для четвертой степени исключение делимости на x и x + 1приводит к многочленам вида x4 +ax3 +bx2 +cx+1, a+b+c = 1(напомним, что коэффициенты мы складываем по модулю 2).Всего есть 4 варианта, которые дают 3 решения:a0011b0101c1001многочленx4 + x + 1x4 + x2 + 1x4 + x3 + 1x4 + x3 + x2 + x + 1приводимыйОткуда взялся еще один приводимый многочлен? В таблице указаны многочлены, у которых нет делителей степени 1.Но многочлен 4-й степени может разлагаться в произведениедвух неприводимых многочленов 2-й степени.
Неприводимыймногочлен 2-й степени единственный, поэтому получаем единственное исключение(x2 + x + 1)2 = x4 + x2 + 1(для возведения в степень, равную характеристике поля, у насесть простая формула (3.1)).3.3.Неприводимые многочлены137Используя неприводимые многочлены, можно строить конечные поля.Рассмотрим поле GF (p) = {0̄, 1̄, . . . , p − 1}, с операциямисложения и умножения по модулю простого числа p.
Возьмеммногочлен n-й степениP (x) = an xn + · · · + a1 x + a0с коэффициентами из этого поля (ai ∈ GF (p), 0 6 i 6 n),неприводимый над полем GF (p). Разложим кольцо многочленов над полем GF (p) по идеалу, порожденному P (x). Получим совокупность остатков от деления на P (x), которая образует поле (поскольку кольцо многочленов евклидово, идеал(P (x)) — максимальный). Элементы этого поля будем обозначать {r(x)} = {f ∈ GF (p)[x] | f (x) = r(x) + Q(x)P (x),Q ∈ GF (p)[x]}.Построенное поле является полем Галуа, т. е.
в нем содержится конечное число элементов. Действительно, разных элементов этого поля, т. е. классов вычетов, имеется столько же,сколько есть разных остатков от деления на P (x). А в остаткеот деления на P (x) может быть любой многочлен степени невыше n−1. Такой многочлен можно записать как b0 +b1 x+. . .++bn−1 xn−1 , где в качестве коэффициентов можно подставлятьлюбые элементы поля GF (p). Поэтому число элементов равноpn .
Соответствующее поле Галуа называется расширением n-йстепени поля GF (p) и обозначается GF (pn ). Обратите внимание на то, что в этом обозначении не используется многочленP (x), с помощью которого мы построили поле. Это не случайно. Верна следующая теорема.Теорема 3.15. Любое конечное поле изоморфно какому-нибудь полю Галуа GF (pn ). Любые два поля, содержащие pnэлементов, изоморфны.Теорема 3.16. Для любой степени n и для любого простогоp существует неприводимый полином степени n над GF (p).Эти две теоремы в совокупности полностью описывают всеконечные поля.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
