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

2.2. Кольца и поля

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

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

R.1. - коммутативная группа.

R.2. - полугруппа, т. е. алгебраическая система, для которой выполняются

R.3. Аксиома дистрибутивности. Для любых трех элементов и с из

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

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

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

Указание. Единичным элементом относительно операции является единичная матрица. Поскольку умножение матриц, вообще говоря, — некоммутативная операция, то кольцо матриц является, таким образом, примером некоммутативного кольца.

Задача 2.17. Пусть дано кольцо Множество всех многочленов

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

Подмножество I кольца называется идеалом кольца если оно удовлетворяет следующим двум условиям:

1.1. Для любых двух элементов из элемент а принадлежит Для любого элемента х кольца и любого а из оба произведения лежат в

Задача 2.18. Множество целых чисел является коммутативным кольцом с единицей. Какой вид имеют идеалы кольца

Решение. Пусть 1 — некоторый идеал кольца и пусть минимальное целое положительное число из Для любого элемента не однозначно определяются такие числа что

Так как то Следовательно, а Если допустить, что то сразу получаем противоречие, так как по предположению минимальное число в Следовательно, и

Это означает, что каждый элемент идеала делится на Таким образом, идеал это множество всех чисел, кратных Будем обозначать этот идеал через

В теории групп с помощью нормальных делителей строятся факторгруппы. В теории колец роль нормальных делителей выполняют идеалы.

Если идеал кольца то в можно ввести новое бинарное отношение следующим образом:

Это бинарное отношение является отношением эквивалентности. Для того чтобы убедиться в этом, проверим справедливость аксиом отношения эквивалентности:

1) Так как

2) Пусть Тогда, поскольку имеем а это означает, что

3) Пусть Тогда, поскольку то из 1.1 получаем, что Это означает, что а

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

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

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

а именно

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

кольцо. Это кольцо называется кольцом классов вычетов и обозначается через

Утверждение 2.19. Как следует из задачи 2.18, идеалы кольца это множества вида Выберем одно из чисел и с помощью идеала построим кольцо классов вычетов Аддитивная группа этого кольца изоморфна факторгруппе из утверждения 2.8. Умножение определяется равенством (Остаток от деления на

Задача 2.20. Построить таблицы сложения и умножения для кольца класса вычетов

Решение:

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

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

F.1. - коммутативная группа.

Пусть 0 — единичный элемент группы множество, полученное из удалением элемента 0.

F.2. - коммутативная группа.

F.3. Закон дистрибутивности. Для любых трех элементов и с из

Утверждение 2.21. Множество действительных чисел и множество С комплексных чисел являются полями относительно обычных операций сложения и умножения и называются соответственно полем действительных чисел и полем комплексных чисел. Однако коммутативное кольцо с единицей полем не является.

Утверждение 2.22. Свойства полей. (Единичный элемент поля по сложению обозначается через 0.)

1) Для любого элемента а поля а

2) Для любых двух ненулевых элементов поля

3) Для любых двух элементов поля

4) Если и то

Доказательство.

1) По определению единичного элемента аддитивной группы . В силу закона дистрибутивности а Так как поле является группой по сложению, то из единственности единичного элемента аддитивной группы (см. задачу 2.4) имеем а Аналогично доказывается, что

2) Аксиома устанавливает, что множество является группой относительно операции Сформулированное выше свойство 2 поля есть просто следствие свойства замкнутости операции в группе

3) Справедливость следующих равенств следует непосредственно из определения поля: Из существования и единственности обратного элемента (см. задачу 2.4) имеем Аналогично доказывается, что а

4) Так как то существует обратный к а элемент по умножению Умножая обе части равенства с слева на получаем .

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

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

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

Решение. Сначала воспользуемся свойствами 1 и 2 поля, сформулированными в утверждении 2.19. Три графы таблицы умножения можно заполнить, воспользовавшись первым из этих свойств. В силу второго свойства произведение не может быть равно 0, а следовательно, Три графы таблицы сложения, за исключением той, которая соответствует сумме можно сразу же заполнить, воспользовавшись тем, что О является единичным элементом по сложению. Сумма может принимать два значения 0 и 1. Однако, поскольку есть группа по сложению, то, согласно свойствам групповых таблиц,

Примечание. Операция сложения в данном случае представляет собой так называемое сложение по модулю 2. Часто для обозначения этой операции используется знак

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

Если существует биективное отображение поля на поле такое, что для любых двух элементов из

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

Рассмотрим здесь конкретный способ построения конечных полей.

Утверждение 2.24. Если простое число, то -поле.

Доказательство. Выше уже было доказано, что кольцо (утверждение 2.19). Чтобы доказать, что является

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

Итак, для каждого простого числа мы построили конечное поле порядка Элементами этого поля являются классы вычетов кольца по модулю Операции сложения и умножения элементов этого поля задаются равенствами

где остаток от деления числа а на число

Задача 2.25. Построить таблицы сложения и умножения элементов конечных полей порядков 3 и 5.

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

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

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

Если подмножество элементов поля само является полем, то называется подполем расширением Поскольку операции в подполе те же, что и в поле то единичный элемент по сложению 0 и единичный элемент по умножению 1 оба входят в

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

Теорема 2.3. Любое конечное поле является расширением поля где простое число (или поля, изоморфного

Доказательство. Пусть подгруппа (по сложению), порожденная элементом 1 поля и пусть порядок порядок элемента 1 в аддитивной группе поля Тогда

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

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

класс вычетов поля Так как это отображение взаимно однозначно и сохраняет операции, то изоморфны.

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

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

В самом деле, легко проверить, что

Таким образом, порядок любого элемента аддитивной группы поля за исключением элемента 0, равен

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

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

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

Далее, в случае имеем

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

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

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