Неприводимые многочлены. 
Дискретный анализ. 
Основы высшей алгебры

Как было показано выше, кольцо многочленов над полем F — евклидово. Простые элементы этого кольца называются неприводимыми многочленами (над F). В этом разделе мы рассмотрим неприводимые многочлены над полями комплексных, действительных и рациональных чисел, а также над полем вычетов GF (p).

Начнем с того, что проверим справедливость известных школьных фактов о корнях многочленов для колец многочленов с коэффициентами в произвольном поле.

Утверждение 3.6. Остаток от деления многочлена / на многочлен первой степени х — а равен /(а). В частности, / делится па (х — а) тогда и только тогда, когда, а является корнем /, т. е. /(а) = 0.

Доказательство. Разделим / с остатком на х — о, остаток должен иметь степень 0: / = q • (я — а) + Ь. Подставляя вместо х элемент а, получаем f (a) = b. ?

То же самое утверждение можно сформулировать иначе. Рассмотрим гомоморфизм.

который определяется вычислением значения многочлена при х = a: Ev_a: / f (a). У этого гомоморфизма есть ядро: те многочлены, для которых а является корнем. Тогда наше утверждение в точности означает, что Ker Ev_a = (х-а) (идеал, порожденный х — а).

Можно доказать это утверждение, не обращаясь к делению с остатком. Действительно, отображение f (x) i-4 f (x + a) также является гомоморфизмом колец. Более того, оно взаимно однозначно: обратное отображение задается формулой f (x) i-4 f (x—a). Значит, это автоморфизм кольца многочленов. Но тогда наше утверждение достаточно доказать при а = 0, а в этом случае оно очевидно.

Полезным следствием утверждения 3.6 является следующая лемма.

Лемма 3.7. Многочлен степени d имеет не более d корней.

Достаточно вспомнить, что при умножении многочленов степени складываются, и учесть, что многочлены х — а и х — b взаимно просты при а ^ Ь. Отсюда получаем очень важное утверждение:

Лемма 3.8. Если два. многочлена степени не выше d как функции различны, то их значения совпадают не более чем в d точках.

Можно применить предыдущую лемму к разности многочленов. Эта лемма показывает, что многочлены «сильно отличаются один от другого». Именно это свойство многочленов лежит в основе многих их применений в комбинаторике и в теоретической информатике.

Можно также заметить, что корни в лемме 3.7 могут быть и кратными (по определению, а — корень кратности к означает, что / делится на (х — а)^к и не делится на (х — а)^к+1).

Теперь посмотрим, какие многочлены неприводимы над полем комплексных чисел С.

Теорема 3.9 (основная теорема алгебры). Всякий многочлен положительной степени над полем С имеет корень.

Хотя эта теорема и называется основной теоремой алгебры, доказывать ее мы не будем, поскольку ее доказательство относится скорее к анализу, чем к алгебре. (Простое доказательство основной теоремы алгебры см., например, в [5].).

Из теоремы 3.9 и утверждения З. б вытекает, что над полем С неприводимы только многочлены первой степени. (Многочлен первой степени неприводим над любым полем, так как при умножении многочленов их степени складываются, а многочлены нулевой степени обратимы.).

Следующий пример — поле действительных чисел 1R. Чтобы перейти от поля С к полю R, заметим, что отображение z ^ z, сопоставляющее каждому комплексному числу z сопряженное число z, является изоморфизмом поля С на себя (автоморфизмом) и переводит поле К в себя. Отсюда вытекает, что для всякого р € С[х] и всякого, а € С имеет место формула:

где р получается из р комплексным сопряжением коэффициентов. Пусть теперь р Е Щх] сС[х] - многочлен степени > 1, нс имеющий действительных корней (при наличии действительных корней р приводим). Многочлен р имеет комплексный корень а. Так как р = р, то из формулы (3.2) получаем, что р (а) = р (а) = р (а) = 6 = 0. Из утверждения 3.6 получаем, что взаимно простые многочлены х — а и х — а делят р. Но тогда р делится и на их произведение q = (х — а)(х — о), которое 11ринадлежит R [х].

Следовательно, над полем IR. неприводимы:

• а) многочлены первой степени;
• б) те многочлены второй степени, которые не имеют корней в Ш (многочлены с отрицательным дискриминантом).

Все прочие многочлены над Ш приводимы.

Гораздо сложнее обстоит дело с многочленами над полем рациональных чисел Q. Мы ограничимся лишь тем, что докажем существование неприводимых над Q многочленов произвольной степени.

Если q — ненулевой многочлен с рациональными коэффициентами степени п, то, приводя коэффициенты к общему знаменателю, можно записать: q = «("о + ах + • • • + а_пх^п) = = aqo, где все коэффициенты а* — целые числа, не имеющие нетривиального общего делителя, а_п > 0, а € Q. Легко видеть, что многочлен (/о и число, а определены однозначно. Будем называть qo примитивным многочленом, соответствующим многочлену q.

Лемма 3.10 (Гаусс), (uv)о = гщ^о;

Доказательство. В сущности, нужно доказать, что если у каждого из многочленов u. q, vq Е Щх] коэффициенты взаимно просты в совокупности, то у их произведения «ого коэффициенты гак же взаимно просты в совокупности. Для доказательства построим гомоморфизм кольца Ъх на кольцо GF (p)[x], который называется редукцией многочлена по модулю р. Редукция f_p многочлена / получается приведением по модулю р каждого из коэффициентов /. Посмотрев на формулы для суммы и произведения многочленов, видим, что редукция действительно является гомоморфизмом.

Предположим, что у коэффициентов есть общий простой делитель р. Тогда (uoVq)_p и для редукций по модулю р имеем (tto)p (vo)_p ⁼ 0* Поскольку в кольце GF (p)[x] нет делителей нуля (лемма 2.11), то одна из редукций {щ)_р, (vq)_p равна 0. Это противоречит примитивности щ, г"о- ?

Таким образом, вопрос о приводимости многочлена над полем рациональных чисел сводится к вопросу о разложении на множители меньшей степени многочлена с целыми коэффициентами. В этом направлении имеется следующее достаточное условие неприводимости:

Теорема 3.11 (критерий Эйзенштейна). Если для. многочлена q = оо + ах + • • • + а_пх^п с целыми коэффициентами существует такое простое число р, что р а_п, р | а* при г = 0,…, п — 1, р² ао, то этот. многочлен неприводим.

Доказательство. Предположим, что q приводимый многочлен: q = uv. Тогда q_p = u_pv_p. По условию теоремы q_p = ах^п, а Ф 0. Значит, и_р = баг, v_p = сх^т, где к < п и т < п. Поэтому все коэффициенты многочленов и и и, кроме старших, делятся на р, а тогда свободный член многочлена q, (т. е. «о): равный щуо, делится на р², что противоречит условию. ?

Пример 3.12. Многочлен 2. т⁴ — 6х³ + Ъх² -1- 21 неприводим над полем Q. Достаточно взять р = 3 и применить критерий Эйзенштейна.

Пример 3.13. Для всякого п > 0 многочлен х^п — 2 неприводим над Q. Достаточно взять р = 2 и применить критерий Эйзенштейна. Отсюда вытекает, что над нолем рациональных чисел существуют неприводимые многочлены любой степени.

Теперь перейдем к самому важному для нас случаю многочленов над полем GF (p). Начнем с примеров.

Пример 3.14. Найдем все неприводимые многочлены степеней 2, 3, 4 над полем GF (2). В этом поле есть два элемента 0 и 1, операции — сложение и умножение по модулю 2.

Вторая степень: х² + ах + Ь. Ясно, что 6⁰, так как в противном случае имеется разложение на нетривиальные делители х² + ах = х (х + а). Значит, неприводимый многочлен степени 2 имеет вид х² + ах + 1. Поскольку многочленов первой степени всего два: х и х + 1, а делимость на первый мы уже исключили, то осталось исключить делимость на х + 1. Это делается аналогично предыдущему случаю: после замены у = #+1 остается проверить, что свободный член в разложении по степеням у ие равен 0. Этот свободный член равен значению многочлена при х = 1 (в нашем поле —1 = 1). Поэтому получаем условие 1 + а + 1 ф 0, т. е. а ф 0.

Итак, неприводимый многочлен степени 2 единственный: х² 4- х + 1.

Третья степень: ж³ + ах² + bx + l (свободный член ие равен нулю, иначе имеем делитель .т).

Исключим делимость на х + 1, получаем условие а + b Ф 0. Т. е. имеем два решения а = 0, b = 1 и а = 1, b = 0.

Соответственно, имеем два неприводимых многочлена степени 3:

Для четвертой степени исключение делимости на х и х + 1 приводит к многочленам вида х^л+ахФ+Ьх²+сх+1, a+b+c = 1 (напомним, что коэффициенты мы складываем, но модулю 2). Всего есть 4 варианта, которые дают 3 решения:

Откуда взялся еще один приводимый многочлен? В таблице указаны многочлены, у которых нет делителей степени 1. Но многочлен 4-й степени может разлагаться в произведение двух неприводимых многочленов 2-й степени. Неприводимый многочлен 2-й степени единственный, поэтому получаем единственное исключение.

(для возведения в степень, равную характеристике поля, у нас есть простая формула (3.1)).

Используя неприводимые многочлены, можно строить конечные поля.

Рассмотрим поле GF (p) = {О, I,…, р — 1}, с операциями сложения и умножения по модулю простого числа р. Возьмем многочлен n-й степени.

с коэффициентами из этого поля (а, е GF (p). О < г < ??.), неприводимый над нолем GF (p). Разложим кольцо многочленов над полем GF (p) но идеалу, порожденному Р (х). Получим совокупность остатков от деления на Р (х), которая образует ноле (поскольку кольцо многочленов евклидово, идеал (Р (х)) — максимальный). Элементы этого поля будем обозначать {г (;с)} = {/ € GF (p)[x] | f (x) = r (x) + Q (x)P (x), Q € GF (p)[x]}.

I встроенное поле является полем Галуа, т. е. в нем содержится конечное число элементов. Действительно, разных элементов этого поля, т. е. классов вычетов, имеется столько же, сколько есть разных остатков от деления на Р (х). А в остатке от деления на Р (х) может быть любой многочлен степени не выше п— 1. Такой многочлен можно записать как bo+bix+.. .+ + b_n-1;с^{, 1—1}, где в качестве коэффициентов можно подставлять любые элементы поля GF (p). Поэтому число элементов равно р^п. Соответствующее иоле Галуа называется расширением п-й степени поля GF (p) и обозначается GF{pⁿ). Обратите внимание на то, что в этом обозначении не используется многочлен Р{х), с помощью которого мы построили поле. Это не случайно. Верна следующая теорема.

Теорема 3.15. Любое конечное поле изоморфно какому-нибудь полю Галуа GF (pⁿ). Любые два поля, содержащие р^п элементов, изоморфны.

Теорема 3.16. Для любой, степени п и для. любого простого р существует неприводимый полином степени п над GF (p).

Эти две теоремы в совокупности полностью описывают все конечные поля. Другими словами их можно сформулировать так: любое поле содержит р^п элементов, где р — простое, и для каждого простого р и натурального п есть ровно одно (с точностью до изоморфизма) поле GF (pⁿ).

Доказательства этих теорем приводятся ниже. Сейчас заметим только, что нам потребуется строить поля расширением нс только простого поля вычетов GF (p), но и произвольного конечного поля. Конструкция такого расширения дословно совпадает с приводимой выше конструкцией расширения поля.

GF (p).