Таким образом, j = О (mod р) для всех i = 1, 2..... р - 1.

Итак, (а ± р) = а + (ip) . Наконец, либо р = 2 и -р = р, так что (±Р) = ±p либо р нечетно и (iPJo = ±рр. Таким образом,

(а ± Р) = а ± р

и для m = 1 теорема доказана.

Возведем теперь последнее равенство в р-ю степень, ((а ± р)с) = (а ± Р )?, и опять воспользуемся утверждением теоремы при m = 1:

(а ± Р) = а ± Р -. Повторяя это m - 1 раз, получаем

(а ± Р) = а ± Р , что завершает доказательство теоремы. □

Если в кольце с единицей элемент имеет обратный, то он называется обратимым Множество всех обратимых элементов кольца замкнуто относительно умножения, так как, если а к b обратимы, то с = а6 имеет обратный элемент, равный с = i) a .

Теорема 2.2.5.

(i) Относительно умножения в кольце множество обратимых элементов кольца образует группу.

(ii) Если с = ab ис - обратимый элемент кольца, то а имеет правый обратный, а b ~ левый обратный.

(iii) Если с = ab иа не имеет правого обратного или b не имеет левого обратного, то с не является обратимым элементом.

Доказательство. Упражнение. □

Многие примеры колец известны. Например:

1. Множество всех вещественных чисел относительно обычных сложения и умножения образует коммутативное кольцо с единицей. Каждый ненулевой элемент кольца является обратимым.

2. Множество Z всех целых чисел (положительные, отрицательные и нуль) относительно обычных сложения и умножения образует коммутативное кольцо с единицей. Единственными обратимыми элементами кольца служат +1.

3. Множество всех (лхп)-матриц с вещественными элементами

) Используемые для единицы и обратимых элементов кольца английские термины unity9 и unit переводятся на русский язык одним словом единица , так что часто в литературе обратимые элементы называются единицами кольца; мы предпочитаем зафиксировать термин единица в определенном выше смысле.- Прим. перев.

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

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

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

2.3. Поля

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

Определение 2.3.1. По.чем называется множество с двумя операциями - сложением и умножением, - которые удовлетворяют следующим аксиомам:

1. Множество образует абелеву группу по сложению.

2. Поле замкнуто относительно умножения и множество ненулевых элементов образует абелеву группу по умножению.

3. Дистрибутивный закон

(а + Ь) с == ac-j-bc выполняется для любых а, b ш с т поля.

Единичный элемент относительно сложения принято называть нулем и обозначать через О, аддитивный обратный к элементу а обозначать -а, единичный элемент относительно умножения называть единицей и обозначать 1, мультипликативный обратный к элементу а обозначать a~. Под вычитанием (а - Ь) понимается а + (-Ь); под делением (а/Ь) понимается Ь~а.

Следующие примеры полей широко известны:

1. R: множество вещественных чисел.

2. С: множество комплексных чисел.

3. Q: множество рациональных чисел.

Все эти поля содержат бесконечное число элементов. Имеется много других не столь широко известных полей с бесконечным числом элементов. Одно нэ таких полей описывается очень просто и известно как поле Q (/) комплексных рациональных чисел. Оно дается определением

С(/) = 1 + ;Ь1.

где а и i - рациональные числа, а сложение и умножение определяются так же, как для комплексных чисел. При таком определении множество Q (/) удовлетворяет определению 2.3.1 и, следовательно, является полем.

Имеются также поля с конечным числом элементов, и мы будем ими также пользоваться. Поле с q элементами, если оно существует, называется конечным полем или полем Галуа и обозначается GF iq).

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

Это поле известно как GF (2). Никаких других полей с двумя элементами не существует (за исключением, конечно, изоморфных копий поля GF (2)).

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

Поле GF (3) = - -

Заметьте, что в GF (4) умножение не есть умножение по модулю 4, а сложение не есть сложение по модулю 4 Поле GF (5) = 0, 1, 2, 3, 4 с операциями

Это примеры очень малых полей. Мы найдем применения и для значительно больших полей, таких как GF (2 + 1).

Для произвольного поля, как бесконечного, так и конечного, применимы почти все известные алгоритмы вычислений. Это происходит потому, что большинство процедур, используемых в полях вещественных и комплексных чисел, зависит только от даваемой определением 2,3.1 формальной структуры поля и не зависит от частных характеристик конкретного поля. Б произвольном поле F имеется даже преобразование Фурье: ,

<; = 0.....п~Л,

где со - корень степени п из единицы в поле f, а v и V - векторы длины п над полем F. Преобразование Фурье длины п в поле F существует тогда и только тогда, когда поле содержит корень степени п из единицы. Если преобразование Фурье существует, то оно ведет себя ожидаемым образом. В частности, должно существовать и обратное преобразование Фурье, и должна выполняться теорема о свертке, так как если просмотреть доказательства тих свойств, то можно увидеть, что о поле F не делается никаких предположений, за исключением того, что оно является даваемой определением 2.3.1 формальной структурой.

Аналогично, двумерное преобразование сЬурье в поле F

п-1 п -! А = О.....п - 1,

С-О i =0 я - и, . . ., П 1,

существует, если в поле F имеется элемент со порядка п и элемент ц порядка п . Если таких элементов в поле нет, то указанное преобразование не существует.

Например, в поле GF (5) порядок элемента 2 равен 4. Следовательно, в поле GF (5) существует 4-точечное преобразование Фурье

У=Ъ 2Ч, к = й, 1, 2, 3, и двумерное (4х4)-преобразование Фурье

П..г= Е S 2-2 -.,-. г.

Компоненты векторов v и V принадлежат полю GF (5), и вся арифметика является арифметикой поля GF (5). Если

2- Введение в астрактную алгебру

ТО одномерное преобразование Фурье вектора v равно

Определение 2.3.2. Пусть F - поле. Подмножество в F называется подполем, если оно является полем относительно наследуемых операций сложения и умножения; исходное поле F в этом случае называется расширением подполя.

Поле рациональных чисел является подполем поля вещественных чисел, которое в свою очередь является подполем поля комплексных чисел. Поле комплексных рациональных чисел не является подполем поля вещественных чисел, но является подполем поля комплексных чисел. Легко видеть, что конечное поле GF (2) является подполем поля GF (4), так как элементы О и 1 складываются и умножаются в поле GF (4) так же, как в поле GF (2). Однако GF (2) не является подполем ни поля GF (3), ни поля GF (5).

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

Каждое поле содержит в качестве подмножества множество своих целых

..., -(1 -ь 1 -Ь 1), -{1 + 1), -1, О, 1, I -I- 1,

1 + 1+1, ...ь

Целые поля обычно записываются просто как О, ±1, ±2, ±3, ... . Поле может содержать только конечное число целых, и в этом случае такое число называется характеристикой поля. (Оно всегда простое.) Все элементы полей GF (3) и GF (5) являются целыми, так что характеристики полей равны соответственно 3 и 5. Так как в поле GF (4) целыми являются только О и 1, то характеристика этого поля равна 2. Характеристика и поля вещественных чисел, и поля комплексных чисел равна оо. Каждое поле характеристики оо содержит поле рациональных чисел (или его изоморфную копию).

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

2.4. Векторные пространства

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

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

Определение 2.3.2. Примитивным элементом поля Галуа GF (q) называется элемент порядка (i? - 1) относительно умножения. Он порождает мультипликативную группу поля.

Например, в поле GF (5) степени элемента 3 равны: 3 = 3, З = 4, 3 = 2, 3 = 1. Следовательно, 3 - примитивный элемент поля GF (5).

2.4. Векторные пространства

Для заданного поля F п-последовательность (и fj, c .i) элементов поля называется вектором длины п над полем F. Множество всех таких векторов длины п вместе с двумя заданными на нем операциями - сложением векторов и умножением на скаляр ---называется векторным пространством над полем F. При рассмотрении векторных пространств элементы поля F, над которыми строются векторы, называются скалярами. Умножение на скаляр - это операция, связывающая вектор v с элементом поля с по правилу

с (Ио, 1.....f -l) = {CV , COi.....OT i).

Векторное сложение является операцией сложения двух векторов,

V = v + v, выполняемого по следующему правилу:

(vi, v\.....+ ( ;, vu . .., n-i) =

= (ио -f oo, v[ -\-vi.....v , + ; ,)

Векторное пространство n-последовательностей представляет собой один пример векторных пространств. Векторное пространство над полем F можно определить абстрактно как множество

V элементов (именуемых векторами) с двумя заданными на нем операциями. Первая операция определена ка парах элементов из V, называется сложением векторов и обозначается плюсом. Вторая операция определена на элементе из V и элементе из F, дает в результате элемент из V и называется у.нножением на скаляр; для обозначения такой операции эти элементы записываются