4.3. МИНИМАЛЬНЫЕ МНОГОЧЛЕНЫ

Согласно теореме Ферма (следствие 3) каждый элемент поля удовлетворяет уравнению

Все коэффициенты этого многочлена лежат в поле и он нормирован (старший коэффициент равен 1). Элемент однако, может быть и корнем многочлена более низкой степени.

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

Пример. В поле где возможными коэффициентами для минимального многочлена являются 0 или 1, имеем:

В § 4.4 мы увидим, как находить минимальные многочлены.

Свойства минимальных многочленов. Предположим, что минимальный многочлен элемента

Свойство. неприводим.

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

Свойство. Если некоторый многочлен [с коэффициентами из такой, что то

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

Свойство.

Доказательство. Утверждение вытекает из и следствия 3.

Свойство.

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

Свойство. Степень минимального многочлена примитивного элемента поля равна Такой многочлен называется примитивным.

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

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

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

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

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

Рис. 4.2. Два способа задания

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

Конечные поля можно также интерпретировать как неприводимые циклические коды (см. гл. 8).

Наоборот, конечное поле всегда существует:

Теорема 7. Для любого простого числа и любого целого существует поле порядка которое обозначается через

GF(p^m). (Согласно предыдущей теореме это поле по существу единственно.)

Доказательство. Для поле было определено в § 4.1. Предположим, что и обозначим Идея доказательства состоит в последовательном построении цепочки полей до тех пор, пока не будет построено поле, скажем, содержащее все корни многочлена Тогда согласно упражнению (6) все корни многочлена образуют необходимое поле порядка Пусть — неприводимый делитель степени не менее 2 многочлена над (если таковой имеется); используя конструкцию теоремы 1 при построим новое поле Пусть теперь — неприводимый делитель степени не менее 2 многочлена над (если таковой имеется); используя конструкцию теоремы 1 при построим новое поле После конечного числа шагов будет построено поле, содержащее все корни многочлена Это завершает доказательство теоремы.

Другое доказательство. Согласно доказываемому ниже следствию 16, над полем всегда существует неприводимый многочлен степени Тогда утверждение теоремы вытекает непосредственно из конструкции теоремы 1.

Упражнение. (10). Показать, что отображение задает изоморфизм поля на себя.

Подполя в Мы можем проитерировать конструкцию теоремы 1 (так, как это было сделано при доказательстве теоремы 7). Сначала присоединим к корень неприводимого над многочлена степени и построим Пусть теперь неприводимый над многочлен степени Образуем новое поле, присоединив к нему корень многочлена Рассуждения, использованные в гл. 3, приводят нас к выводу, что это новое поле содержит элементов. Согласно теореме 6 мы построили поле Таким образом, итерация конструкции теоремы 1 не дает никаких новых полей. Однако такой двухшаговый переход от позволяет доказать следующую полезную теорему.

Теорема содержит подполе (изоморфное) тогда и только тогда, когда делит

Элемент из принадлежит полю тогда и только тогда, когда . В любом поле из равенства следует. что элемент равен 0 или 1.

Для доказательства требуется следующая лемма.

Лемма 9. Если целые числа такие, что то тогда и только тогда, когда (Напомним, что вертикальная черта означает «делит».)

Доказательство. Запишем где Тогда

Число всегда делится на Последнее слагаемое меньше единицы и, следовательно, может быть целым тогда и только тогда, когда 0.

Упражнение. (11). (i). Показать, что в произвольном поле тогда и только тогда, когда

Показать, что где

Доказательство теоремы Если то согласно упражнению (6) поле содержит подполе, изоморфное полю Наоборот, пусть примитивный элемент поля Тогда

Таким образом, и согласно лемме .

(ii). Первое утверждение вытекает непосредственно из следствия 3, а второе — очевидно.

В качестве примера на рис. 4.3 показаны все подполя поля

Сопряженные элементы и циклотомические классы. Свойство. Минимальные многочлены элементов равны. В частности, в поле равны минимальные многочлены элементов

Доказательство проведем на примере. Пусть минимальный многочлен элемента из GF(24). Тогда по лемме

Рис. 4.3. Подполя поля

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

Элементы поля, минимальные многочлены которых равны, называются сопряженными. (По этой же причине называются комплексно-сопряженными числами: над полем действительных чисел многочлен является минимальным для них обоих.)

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

Определение. Множество целых чисел по модулю относительно операции умножения на распадается на подмножества, которые называются циклотомическими классами по модулю 1.

Циклотомический класс, содержащий состоит из чисел

где наименьшее положительное целое число такое, что Например, циклотомическими классами по модулю 15 (для являются:

Наши обозначения выбраны так, что если наименьшее число в классе, то класс обозначается через Индексы называются представителями классов по модулю

Упражнения. (12). Проверить таблицы циклотомических классов, приведенные на рис. 4.4, для

Рис. 4.4. (см. скан) Циклотомические классы по модулям 7, 31, 63 и 127

(13). Найти циклотомические классы по модулям

Нахождение Пусть - минимальный многочлен элемента . В силу свойства

Из предыдущих рассуждений следует, что если лежит в циклотомическом классе то в поле

(14). Показать, что коэффициенты многочлена в левой части в (4 5), представляющие собой элементарные симметрические функции от лежат в поле [Указание. Воспользоваться теоремой Вывести отсюда, что левая и правая части в (4.5) равны.]

Свойство. Если лежит в то

Более того, из уравнения (4.1) вытекает, что

где пробегает все множество представителей классов по модулю

Упражнения. (15). Показать, что для и 3 выполняются условия: Следовательно, Что можно сказать о

(16). Будем говорить, что неприводимый над GF(q) многочлен принадлежит показателю если порядок всех его корней равен Показать, что в этом случае при

(17). Пусть -минимальный многочлен элемента Показать, что тогда и только тогда, когда наименьшее положительное целое число такое, что

(18). Доказать, что если то где степень многочлена

Задание поля матрицами. Сопровождающая матрица многочлена определяется как матрица размерности вида

Упражнения (19) Показать, что характеристический многочлен матрицы равен многочлену Вывести отсюда, что

(20) Пусть сопровождающая матрица примитивного многочлена степени над полем GF(q) Доказать, что если если Вывести отсюда, что степени матрицы являются ненулевыми элементами поля

Например, возьмем над Тогда элементы запишутся в виде

Сложение и умножение в поле задается как сложение и умножение матриц

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