многочлена х - \ а имеют целые коэффициенты. Так как элемент <о является корнем многочлена g (х), то многочлен g (х ) кратен многочлену f (х):

g {х ) f{x)k (X)

для некоторого многочлена к (х) с целыми коэффициентами. Заменим теперь оба равенства вычетами по модулю р: ж - 1 = Hx)g (х) t [х) (mod р), g (х ) = f (х) к (X) (modp). Согласно теореме 2.2.4, второе равенство записывается в виде ig (х)У = f (х) к (X) (modp).

Рассмотрим разложение этого уравнения над полем GF (р). Каждый простой делитель р (х) многочлена / (х) должен быть простым делителем многочлена (g (х)), и, следовательно, многочлена g (х). Следовательно, (х - I) должен делиться на (р (х)) Но тогда формальная производная пх - от многочлена (х - 1) делится HSU.GF (р) на р (х). По предположению р не делит п, а х не может быть делителем / (x)(mod р), так как / (х) делит х - 1. Полученное противоречие показывает, что g (х) не может быть не равным / (х).

Шаг 2. Теперь докажем утверждение для произвольного h, взаимно простого с п. Запишем разложение h на простые множители:

h = р,р2 ... р,.

Каждый из этих множителей взаимно прост с п, так как Л взаимно просто с п. Согласно утверждению шага 1, если ш - корень многочлена f (х), то м также является корнем этого многочлена. Теперь опять воспользуемся шагом 1: если а - корень многочлена f (х), то и ш; является корнем этого многочлена. Используя индукцию, получаем, что и является корнем /(*).□

5.6. Примитивные элементы

Согласно данному в разд. 2.3 определению, примитивным элементом поля Галуа называется такой элемент а, что каждый ненулевой элемент- поля мокно однозначно записать в виде степени этого элемента. Например, в поле GF (7) выполнянэтся равенства 3 = 3, 3 = 2, 3 = 6, 3 = 4, 3 = 5, З = 1, так что 3 является примитивным элементом поля GF (7). Примитивные элементы полезны при построении полей, так как, коль скоро один из них найден, то, перемножая степени этого примитивного элемента, можно построить таблицу умножения в этом поле. В полях Галуа

Доказательство. Непосредственные вычисления дают:

х -1 = П{х-шУ = П П (х-юО =

!= tin НОД (i. n)=nlk

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

Доказательство. Воспользуемся индукцией по п. Коэффициенты многочлена Qi{x) =х-\ являются целыми. Согласно теореме 5.5.3,

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

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

Доказательство. Приведенность круговых многочленов очевидна. Доказать надо только неприводимость круговых многочленов над полем рациональных чисел. Пусть f (х) обозначает минимальный многочлен элемента ш над полем рациональных чисел. Пусть Л - произвольное целое число, взаимно простое с л, и пусть g (х) - минимальный многочлен элемента над полем рациональных чисел. Предположим, что g (х) = f (х) для каждого такого ft. Тогда многочлен / (д;) должен быть кратным многочлену Q {х), и так как Q (х) приведен и имеет рациональные коэффициенты, / (х) = Q (х). Тогда наша задача сводится к доказательству того, что для каждого взаимно простого с п числа h минимальный многочлен g {х) элемента mj равен многочлену / (д:).

Шаг 1. Докажем сначала это утверждение для случая, когда Л равно простому числу р, не являющемуся делителем п. Пусть g (х) - минимальный многочлен элемента an и предположим, что он не равен многочлену / (х). Тогда

x--l=l(x)g (X) ((X),

для некоторого многочлена ((х), коэффициенты которого целые числа, так как оба многочлена / (д;) и g (д;) являются делителями *

1)чевидно, что bi =1, так что порядок bt делит р]. Он ра-вен числу вида pi. Если п, меньше V(, то Ьь =1. Но

= 1, и, следовательно, порядок элемента bi

равен Pi .

Шаг 2. Порядок элемента b равен д ~- I. Доказательство. Предположим, что = 1. Покажем сначала, что из этого вытекает равенство п = О (mod pi) для всех i = 1, s. Для каждого i можно записать

Ь * 1.

s v-

заменив b на Д Ь( и используя равенство bj = 1, находим

TdKiiM образом,

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

О (modpi) для каждого (. Следовательно, /г =0 {mouq - \). Теорема доказана. □

Теорема 5.6.3. В каждом поле Галуа имеется примитивный ifeuenm.

Доказательство. Так как ненулевые элементы поля GF (д) образуют циклическую группу, то среди них имеется элемент порядка q-l. Этот элемент является примитивным. □

Задачи

I. а. Приводим ли йад полем рациональных чисел многочлен р (х) + -f- 2х х - 2? Если приводим, то разложить его.

б. Приводим ли над полем вещественных чисел многочлен р {х) = д;*--t--f 2x4- -- 2? Если приводим, то разложить его.

в. Приводим ли многочлен р {х)--= х2х-\~ - 2 над полем комплексных чисел? Если приводим, то разложить его.

Над полем рациональных чисел пусть

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

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

Теорема 5.6.1. Пусть Pi, Ра, fi, i - ненулевые элементы поля GF {q)\ тогда:

I x~-l=(x-fii)(x-p,) ... (х-р<, ,).

Доказательство. Множество ненулевых элементов поля GF (q) образует конечную группу по умножению. Пусть р - какой-либо элемент из GF (q), и пусть h - мультипликативный порядок этого элемента. Тогда, согласно теореме 2.1.5, h делит - 1. Следовательно,

так что Р является корнем многочлена л:- - 1. □

Теорема 5.6.2. Группа ненулевых элементов поля GF (q) по умножению является циклической.

Доказательство. Если число q - 1 простое, то теорема тривиальна, ибо порядок всех-элементов, за исключением нуля и единицы, равен q - l, так что каждый такой элемент примитивен. Доказывать теорему надо только для составного числа q- 1. Рассмотрим разложение числа q - I на простые множители!

q-\ = Пр]1.

Так как GF (q) - поле, то среди его 17 - 1 ненулевых элементов должен найтись хотя бы один, не являющийся корнем многочлена i-i)/Pi - поскольку этот многочлен может иметь не более (д - l)/pi корней. Следовательно, для каждого i можно найти

такой элемент Oj поля GF (q), что а ф 1. Пусть bi = at ,

и пусть b = П bi. Покажем, что порядок b равен q - 1, и,; 1

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

Шаг 1. Порядок элемента Ь( равен pt. Доказательство.

Замечания

Материал данной главы обычен для математической литературы Хорошее

П%оТ Свой.ЗпТг У Хардии рЖ 2

(1УЬи). Свойства полей Галуа описываются во многих книгах по абстрактной

Ваолена uf?S R f Р* t] (1941). а такжеТан дер является JonM.? материала, однако, это стандартное изложение является формальным, уделяет основное внимание абстрактным свойствам и IZlrJ ало примеров и приложений. Большее внимие в1ислит1льным аспектам полей Галуа уделил Берлекэмп [5] (1968). Более детальное изложение ГКи 7бГ(Т979). --нов 1ожн!> найти J ~мГлГГн

а. Найти НОД [pi (i), р, И1,

б. Найти НОК [р, W, р, (г)),

В-. Найти многочлены Л (х) В {х), удовлетворяющие равенству НОД [pi (дг), л (дг)I = А (X) р, W + а W р, ( ).

5.3. Пусть т(х)= х + 1+ 1, т, (х) = 1, т, (д:) = - I. Пусть даны Cl (х) = с (д:) (mod mi (д:)),

Cj (х) = с W (modmjW),

CsW=cW (modmsW), где степень многочлена с [х) не превосходит 5. Найти все многочлены, необходимые для вычисления многочлена с (х) по этим вычетам.

5.4. Сколько круговых многочленов де,1ят х - 1? Найти их.

5.5. Пусть р (х) = 2 х. Используя соотношение

лгв - 1 - (х- \)р{х), найти и -!- х> х°].

5.6. Доказать, что для формальной производной многочлена выполняется

равенство

[г (х) S (X) У = г (х) S (X) + г (X) six).

и что если {х) делит г (х). то а [х) делит г (х).

5.7. Докйзать, что в кольце Z/(15) целых чисел по модулю 15 многочлен р (х) = ~ х- 1 имеет более двух корней. Этот же многочлен над полем имеет только два корня. В каком месте в случае кольца не проходит доказательство теоремы?

5.8. Многочлен р (х) = х-\- ххх1 непрчводим над полем GF (2), Следовательно, кольцо многочленов по модулю р (х) является полем GF (16).

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

б. Показать, что многочлену д: + 1 соответствует примитивный многочлен.

в. Найти минимальный многочлен элемента 1.

5.9. Над полем GF (16):

а. Сколько имеется различных приведенных многочленов второй степени вида х=+ tix-J- fc, Ь 0?

б. Сколько имеется различных многочленов вида {х - Р) ( - V) Pi V

В. Доказывает ли это существование неприводимых многочленов второй степени? Сколько простых многочленов второй степени имеется над полем GF (16)?

5.10. а. Построить расширение поля вещественных чисел R, используя простой многочлен 1. Объяснить, почему это расширение является полем комплексных чисел С, которое можно построить также, используя простой многочлен + 1.

б. Построить расширение поля рациональных чисел Q, используя простой многочлен д:*4- 1. Объяснить, почему это расширение отличается от расширения поля рациональных чисел с помощью простого многочлена jf -(- 1. 5.И. Построить поле GF (7). задавая его таблицами сложения и умножения.

5.12. Вычислить 33° (mod 7).

5.13. Доказать, что кольцо вычетов Zq является кольцом.

5.14. Найти элементы порядка р (р - 1) в каждом из следующих полей: ., GF (9), GF (25), GF (27), GF (49). [

5.15. Доказать, что многочлен лс* + + 1 неприводим над полем рациональных чисел.