Главная > Помехоустойчивое кодирование > Теория кодирования
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

2.4. Многочлены

Пусть поле, множество всех многочленов

от переменной X над полем Если в то говорят, что многочлен имеет степень Степень многочлена будем обозначать через Множество всех многочленов, имеющих степень и менее, обозначим через

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

Задача 2.36. Перечислить все многочлены степени 2 и менее над полем и указать их степени.

Решение.

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

Если в многочлен из последней задачи подставлять вместо X элементы 0 и 1 поля то он будет принимать те же значения, что и многочлен Однако как многочлены и различны. Заметим, что число различных многочленов степени и меньше над полем порядка равно

Введем далее операции сложения и умножения многочленов следующим образом. Для любых двух многочленов положим

В частности, если то

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

Утверждение 2.37. Многочлены из обладают следующими свойствами:

Доказательство. Свойства 1—4 можно доказать точно так же, как и соответствующие свойства из утверждения 2.28. Докажем свойство 5. Из предположений и свойства 4 непосредственно следует, что Так как то в силу свойства так что

Примечание. Метод доказательства свойства 4 из утверждения 2.22 здесь неприменим, так как элемент, обратный к может и не существовать.

Утверждение 2.38. Для любых двух ненулевых многочленов таких,

Утверждение 2.39. Для любых двух многочленов существуют, и притом единственные, многочлены такие, что

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

Тогда

Поскольку степень многочлена в правой части последнего равенства меньше, чем степень то это равенство может иметь место лишь в том случае, когда следовательно,

Если в формуле (2.11) остаток равен нулю, то говорят, что делит Если в нет ни одного многочлена степени, большей 0, который делил бы (за исключением скалярных кратных то называется неприводимым. Элемент а поля такой, что называется корнем . В этом случае также говорят, что уравнение имеет корень а в поле

Утверждение 2.40. Если уравнение имеет корень а в поле то существует такой многочлен что Если степень равна то уравнение имеет не более корней.

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

Подставляя в обе части последнего равенства , получаем

Поскольку а является корнем то т.е. Следовательно,

Далее, если уравнение имеет различных корней то существует такой многочлен что Это означает, что имеет не более корней.

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

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

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

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

частности, что многочлены оба делятся на многочлен ненулевой степени. Мы получили противоречие, поскольку по условию взаимно просты. Таким образом, любой многочлен минимальной степени в является многочленом нулевой степени, т.е. элементом поля Пусть с — один из таких элементов, По определению

где Умножая обе части последнего равенства на получим равенство (2.12).

Многочлены из коэффициенты при наивысшей степени X которых равны 1, называются нормированными многочленами.

Утверждение 2.42. Любой многочлен степени 1 и выше над полем можно представить в виде произведения элемента поля и нормированных неприводимых многочленов над тем же полем. Это разложение единственно с точностью до порядка следования сомножителей (доказательство см. в [3]).

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

Задача 2.43. Найти все неприводимые многочлены степени 4 и менее над полем

Решение. Многочлены первой степени. Имеется два многочлена первой степени По определению оба они неприводимы.

Многочлены второй степени. Многочлен второй степени неприводим тогда и только тогда, когда он не делится ни на X, ни на Это эквивалентно тому, что Следовательно, лишь один из многочленов второй степени, а именно является неприводимым.

Многочлены третьей степени. Многочлен с является неприводимым тогда и только тогда, когда он не делится ни на X, ни на Это эквивалентно тому, что или

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

Многочлены четвертой степени. Многочлен является неприводимым тогда и толькр тогда, когда он не делится ни на один из неприводимых многочленов первой или второй степени. Поскольку имеется только один неприводимый многочлен второй степени, то все многочлены четвертой степени, не являющиеся неприводимыми, за исключением многочлена ( должны делиться на один из многочленов первой степени. Следовательно, для неприводимых многочленов четвертой степени Многочленами, удовлетворяющими этим условиям, являются следующие: Все они, за исключением являются неприводимыми.

Примечание. Таблица неприводимых многочленов до 34-й степени включительно над полем порядка 2 приведена в [1]. описан способ нахождения неприводимых многочленов и подсчета числа последних. В приложении в конце данной книги дана таблица неприводимых многочленов до 14-й степени включительно над полем порядка 2, до 6-й степени над полем порядка 3 и до 4-й степени над полем порядка 5.

Задача 2.44. Показать, что многочлен рассматриваемый как многочлен над полем порядка 3, является неприводимым.

Решение. В данном случае необходимо проверить, что не делится ни на один из многочленов первой степени. Для этого достаточно убедиться в том, что Действительно,

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

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

Заменим в многочлене переменную X на Если теперь рассматривать как многочлен от У, то коэффициентами последнего будут многочлены от X:

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

где Обозначив через получим

Введенный таким образом многочлен называется производной

Утверждение 2.45. Для любого элемента и любых многочленов имеют место следующие равенства:

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

Третье равенство доказано. В частности, если то из третьего равенства легко получить, что

Отсюда в свою очередь следует, что

Из первого, второго и пятого равенств получаем четвертое равенство.

Задача 2.46. Пусть поле характеристики 2. Найти производную многочлена

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

Например, если то

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

Утверждение 2.47. Пусть поле, -неприводимый многочлен, такой, что Многочлен делится на тогда и только тогда, когда наибольший общий делитель многочленов делится на

Доказательство. Допустим, что Тогда

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

Утверждение 2.48. Пусть конечное поле порядка Каков бы ни был двучлен в не существует ни одного неприводимого многочлена такого, что

Доказательство. Так как то справедливость утверждения 2.48 непосредственно следует из утверждения 2.47. Доказанное утверждение означает, что двучлен не имеет кратных корней.

Утверждение 2.49. Многочлен

над полем равен 0 только в том случае, если все его коэффициенты а равны

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

Каждый коэффициент многочлена от в левой части последнего равенства является элементом кольца Если это кольцо рассматривать как кольцо а как X, то из сформулированного в начале доказательства утверждения будет следовать, что

Но тогда по предположению индукции все коэффициенты многочленов должны быть равны 0, а следовательно, равны 0 и коэффициенты

<< Предыдущий параграф Следующий параграф >>
Оглавление