4.3. КОЛЬЦА МНОГОЧЛЕНОВ

Многочленом над полем называется математическое выражение

где символ х называется неопределенной переменной, коэффициенты принадлежат полю а индексы и показатели степеней являются целыми числами. Нулевым многочленом называется многочлеп Приведенным многочленом называется многочлен, старший коэффициент которого равен Два многочлена равны, если равны все их коэффициенты

Степенью ненулевого многочлена называется индекс старшего коэффициента степень многочлена обозначается через Степень ненулевого многочлена всегда конечна. Степень нулевого многочлена по соглашению полагается равной отрицательной бесконечности

Множество всех многочленов над полем образует кольцо относительно сложения и умножения, определяемых по обычным правилам сложения и умножения многочленов. Такое полиномиальное кольцо можно определить для каждого поля Галуа Это кольцо обозначается через В исследованиях по кольцам элементы поля иногда называются скалярами.

Суммой двух многочленов из называется многочлен из определяемый равенством

где, конечно, члены с индексом, большим наибольшей из степеней многочленов равны нулю. Степень суммы не превосходит наибольшей из этих двух степеней. Например, над

Произведением двух многочленов из называется многочлен из определяемый равенством

Например, над

Степень произведения равна сумме степеней множителей.

Кольцо многочленов во многих отношениях аналогично кольцу целых чисел. Чтобы сделать эту аналогию очевидной, в изложении данного параграфа мы следуем § 4.1. Скажем, что многочлен делится на многочлен или что делит если существует многочлен такой, что Многочлен делящийся только на многочлены или , где — произвольный ненулевой элемент поля называется неприводимым многочленом. Приведенный неприводимый многочлен называется простым многочленом.

Наибольший общий делитель двух многочленов обозначается через и определяется как приведенный многочлен наибольшей степени, делящий одновременно оба из них. Наименьшее общее кратное двух многочленов обозначается через и определяется как приведенный многочлен наименьшей степени, делящийся на оба из них. Как мы увидим, наибольший общий делитель и наименьшее общее кратное определены единственным образом, так что наше определение корректно. Если наибольший обилий делитель двух многочленов равен I, то они называются взаимно простыми.

Если одновременно делится на и делит то где а — элемент поля Это доказывается следующим образом. Должны существовать многочлены и такие, что и следовательно, Но степень правой части равна сумме степеней и Так как эта величина должна быть

равной степени левой части, то и должны иметь нулевую степень и, таким образом, являться скалярами.

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

Определение 4.3.1. Пусть

— многочлен над Формальная производная от определяется как многочлен вида

где коэффициенты называются числами поля и вычисляются как сумма членов в поле

Легко проверить, что сохраняются многие полезные свойства производных, а именно что

и что если делит то делит

В кольце многочленов, так же как и в кольце целых чисел, деление в общем случае невозможно. Однако для многочленов над полями тоже имеют место сокращение и деление с остатком. Алгоритм деления для многочленов дается следующим утверждением.

Теорема 4.3.2 (алгоритм деления для многочленов). Для каждой пары многочленов с существует единственная пара многочленов (частное) и (остаток), таких, что

Доказательство. Частное и остаток находятся по элементарному правилу деления многочленов. Они единственны, так как если

то

В правой части стоит ненулевой многочлен, степень которого меньше а в левой — ненулевой многочлен, степень которого не меньше Следовательно, оба многочлена равны нулю, и представление единственно.

Практическое вычисление частного и остатка выполняется с помощью простого правила деления многочленов «уголком». Обычно мы будем больше интересоваться не частным, а остатком. Остаток можно также записать в виде Часто остаток называют вычетом многочлена с по модулю многочлена Несколько отличным понятием является сравнение

которое означает, что при делении на многочлены дают один и тот же остаток, но степень многочлена с не обязательно меньше степени многочлена

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

Теорема 4.3.8. Пусть кратен многочлену Тогда для любого

Доказательство. Пусть для некоторого Раскрывая правую часть, получаем

где степень остатка меньше Раскрывая левую часть, имеем

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

Доказательство сводится к упражнению: использовать алгоритм деления для выражений в сбеих частях равенства и приравнять остатки.

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

Теорема 4.3.5 (теорема об сднозиачнсм разложении). Ненулевой многочлен над некоторым полем однозначно (с точностью до порядка следования множителей) разлагается в произведение элемента поля и простых многочленов над этим полем.

Доказательство. Ясно, что входящим в произведение элементом поля должен быть коэффициент где степень многочлена Можно пренебречь этим элементом и доказывать теорему для приведенных многочленов.

Предположим, что теорема не верна. Пусть приведенный многочлен наименьшей степени, для которого не верна теорема. Тогда имеются два разложения:

где простые многочлены

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

Без потери общности предположим, что степень многочлена не больше степени многочлена Тогда

где Далее,

Разложим многочлен и многочлен, стоящий в квадратных скобках, на простые множители, разделив, если надо, на соответствующий элемент поля так, чтобы все множители были приведенными. Поскольку не содержится в левой части, мы получили два различных разложения приведенного многочлена, степень которого меньше степени Это противоречие доказывает теорему.

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

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

Теорема 4.3.6 (алгоритм Евклида для многочленов). Наибольший общий делитель двух многочленов над

полем можно вычислить с помощью итеративного применения алгоритма деления Если то последовательность вычислений такова:

и процесс обрывается, как только получается равный нулю остаток. Тогда , где а — некоторый скаляр.

Доказательство. Отправляясь от первого уравнения, видим, что делит и делимое, и делитель, и, следовательно, остаток. Проводя это рассуждение далее по всем уравнениям, видим, что делит Отправляясь от последнего уравнения, видим, что делит делитель и остаток, так что он дел делимое. Проводя это рассуждение по всем уравнениям вплоть до первого, видим, что делит Так как делит и делится на него, то получаем утверждение теоремы.

Следствие 4.3.7. , где и многочлены над

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

Для произвольного элемента поля можно вычислить значение мнегочлена над в этой точке, подставив элемент Еместо неопределенной переменной. Например, пусть над

Тогда (см. рис. 4.1) получаем

В случае поля вещественных чисел известной процедурой является вычисление значений многочлена в расширении этого поля; широко применяется вычисление значений многочлена с вещественными коэффициентами в поле комплексных чисел. Аналогично

Рис. 4.1. Примеры конечных полей.

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

Тогда (см. рис. 4.1) для элементов поля имеем

Если то элемент называется корнем многочлена или корнем уравнения Многочлен не обязательно имеет корни в своем собственном поле. Многочлен не имеет корней в а также в

Теорема 4.3.8. Элемент является корнем многочлена тогда и только тогда, когда делит Более того, корнями многочлена степени являются не более элементов поля. Доказательство. Согласно алгоритму деления,

где степень меньше единицы. Таким образом, является элементом поля Следовательно, и соответственно

Обратно, если делит то

так что и, таким образом, корень многочлена

Разложим теперь многочлен в произведение элемента поля и простых множителей. Степень многочлена равна сумме степеней простых множителей, и для каждого корня имеется один такой множитель. Следовательно, существует не более корней.