2. Конечные поля

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

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

2.1. Группы

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

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

G.1. Для любых двух элементов из однозначно определен элемент .

G.2. Для любых трех элементов и с из

G.3. В G существует элемент называемый единичным, такой, что для любого элемента а из

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

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

Группа называется коммутативной или абелевой, если, кроме аксиом справедлива также следующая аксиома коммутативности:

AG. 5. Для двух произвольных элементов из

Если для обозначения групповой операции группы для которой выполняются аксиомы и вместо знака О используется знак то группа называется по традиции аддитивной группой. Часто для обозначения групповой операции, вообще говоря некоммутативной, используется мультипликативная запись, т.е. вместо знака О используется знак а вместо записи запись или При мультипликативной записи обратный элемент к а обозначается через В результате того, что одни и те же стандартные обозначения, например знаки и используются для разных операций в различных группах, возникает некоторый сознательно создаваемый беспорядок в использовании обозначений. С другой стороны, это можно рассматривать и как некоторый конструктивный способ расширения смысла знаков. Так, например, евклидово расстояние в двумерном случае определяется равенством и обобщается на -мерный случай следующим образом: Однако заметим, что аналогично в гл. 1 были определены также расстояния

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

Понятие расстояния возникло в результате абстрагирования общих свойств «частных» расстояний. Однако после того, как расстояние определено указанным выше образом, все функции двух переменных, обладающие указанными выше тремя свойствами, могут быть названы единым термином — расстояние.

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

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

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

Утверждение 2.2. Если в множестве определить операцию с помощью табл. 2.1 (заметим, что эта операция коммутативна), то множество становится группой относительно введенной операции (другими словами, есть группа).

Таблица 2.1 (см. скан)

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

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

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

1) Она состоит лишь из элементов множества

2) Строки и столбцы ее являются перестановками последовательности (0,1,2); все строки (столбцы) различны.

Аналогичными свойствами обладают все групповые таблицы.

Утверждение 2.3. Множество комплексных чисел где со — корень третьей степени из единицы, образует группу относительно обычной операции умножения комплексных чисел.

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

Таблица 2.2 (см. скан)

Гомоморфизм и изоморфизм групп. Если отображение множества в таково, что для любого элемента существует элемент такой, что то говорят, что сюръективно. Если отображение таково, что для любых двух элементов из то говорят, что инъективно. Отображение биективно, если оно одновременно сюръективно и инъективно [3]. Пусть даны две группы и Если отображение множества таково, что для любых двух элементов

то называется гомоморфным или гомоморфизмом в Далее, если, кроме того, отображение множества

в сюръективно или инъективио, то говорят, что гомоморфизм соответственно сюръективен или инъективен. Если гомоморфизм одновременно и сюръективен и инъективен, то отображение группы в называется изоморфным или изоморфизмом. Две группы называются изоморфными, если существует изоморфное отображение Две изоморфные группы идентичны с точки зрения их свойств и отличаются лишь формой представления элементов. С помощью биективного отображения можно установить взаимно однозначное соответствие между элементами изоморфных групп так, что их групповые таблицы будут иметь одинаковый вид (с точностью до обозначения элементов). Группы, задаваемые табл. 2.1 и 2.2, изоморфны. Чтобы убедиться в этом, достаточно между элементами этих групп установить следующее взаимно однозначное соответствие:

Число элементов в группе называется порядком Группа, порядок которой конечен, называется конечной. Если порядок группы бесконечен, то она называется бесконечной. Так как изоморфизм задает отношение эквивалентности, то все группы можно разбить на классы эквивалентности, каждый из которых можно было бы назвать абстрактной группой. При этом группы, принадлежащие одному классу эквивалентности и имеющие одинаковую «структуру», можно назвать конкретными группами. Определение числа классов эквивалентности групп заданного конечного порядка является одной из нерешенных проблем теории конечных групп. В то же время, как это будет доказано ниже, все конечные поля, имеющие одинаковое число элементов, изоморфны. Структура всех конечных полей также хорошо известна. Здесь мы не будем глубоко вникать в проблемы теории конечных групп, однако для справок укажем число классов эквивалентности групп порядка

Задача 2.4. Показать, что все группы обладают следующими свойствами:

1. В группе содержится только один единичный элемент (единственность единичного элемента).

2. Для каждого элемента а группы обратный элемент определяется единственным образом (единственность обратного элемента).

3. Из следует, что Из также следует, что

4. Пусть два произвольных элемента группы. Тогда решениями уравнений являются соответственно элементы и эти решения единственны.

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

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

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

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

Пусть подгруппа группы произвольный элемент из Множество обозначаемое ниже через называется левым смежным классом группы по подгруппе порождаемым элементом Аналогично множество обозначаемое через называется правым смежным классом группы по подгруппе порождаемым элементом

Задача 2.6. Пусть группа порядка 6, задаваемая табл. 2.3, а подгруппа группы задаваемая табл. 2.4. Найти все правые смежные классы группы по подгруппе Показать, что любые два левых смежных класса либо совпадают, либо не имеют общих элементов.

Кроме того, проверить, что объединение всех смежных классов совпадает с множеством

Таблица 2.3 (см. скан)

Таблица 2.4 (см. скан)

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

Отсюда непосредственно следует справедливость указанных выше свойств.

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

Здесь и в дальнейшем через обозначается число элементов в множестве Равенство (2.1) доказывается следующим

образом. Пусть Тогда, пользуясь определением можно установить следующее соответствие между элементами

Отсюда следует, что Предположим, что Тогда найдутся два различных элемента таких, что . В силу свойства 3 группы, указанного в задаче 2.4, получим что противоречит предположению о том, что элементы различны. Следовательно, справедливость равенства (2.1) доказана. В приведенном выше упражнении Эти равенства являются следствием следующего общего свойства групп. Если смежные классы На и группы по подгруппе имеют хотя бы один общий элемент, то они совпадают, т. е. . В самом деле, если два смежных класса На и имеют хотя бы один общий элемент, то где Умножая обе части последнего равенства слева получим где Тогда

где Точно так же можно доказать, что . Следовательно,

Отсюда следует справедливость следующей теоремы Лагранжа.

Теорема 2.1. (Лагранж.) Порядок любой подгруппы конечной группы является делителем порядка группы.

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

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

Из теоремы Лагранжа непосредственно следует справедливость следующего утверждения.

Следствие 2.1. Если конечная группа, то

Задача 2.7. Доказать, что группа которая рассматривалась в предыдущей задаче, может содержать подгруппы порядка 1, 2, 3 и 6, но не 4 и 5.

Решение. Порядок равен 6, и все его делители — это числа 1, 2, 3 и 6. Подгруппой порядка 1 является подгруппа а подгруппой порядка 6 — сама группа

Нормальные делители. Подгруппа группы называется нормальным делителем, если для любого элемента

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

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

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

Прежде всего покажем, что для этой алгебраической системы выполняется аксиома Для этого вначале покажем, что множество определяемое соотношением (2.2), является одним из смежных классов группы по нормальному

делителю Н. В самом деле,

Так как Н является нормальным делителем, то Следовательно,

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

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

Утверждение 2.8. Пусть Обозначим через множество кратных целого положительного числа а именно Так как группа коммутативна, то алгебраическая система является нормальным делителем группы Следовательно, можно определить факторгруппу Эту факторгруппу часто обозначают через

Доказательство. То, что Я является подгруппой группы проверяется легко. Рассмотрим несколько более детально группу Обозначим через смежный класс, содержащий х. Всего имеется следующих смежных классов:

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

то эти смежные классы будут образовывать группу.

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

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

Так как группа конечна, то существуют такие числа что

Но тогда, поскольку

Минимальное целое положительное число такое, что называют порядком элемента а. Если группа конечна, то порядок каждого элемента группы также конечен. Однако в бесконечных группах порядок каждого элемента группы не обязательно должен быть конечным. Например, рассмотрим группу Для элемента 1 этой группы последовательность (2.3) имеет следующий вид:

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

Задача 2.9. Определить порядок каждого элемента группы из задачи 2.6.

В данном случае порядок каждого элемента определялся по числу различных элементов в соответствующей последовательности (2.3). Хотя по определению порядок элемента — это

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

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

Теорема 2.2. Пусть а — элемент порядка группы Тогда подгруппа группы

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

Рассмотренная выше подгруппа Н называется циклической подгруппой. В частности, если в группе существует элемент и, такой, что то сама группа называется циклической группой, порожденной элементом а.

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

Следствие 2.2. Порядок каждого элемента конечной группы является делителем порядка

Утверждение 2.10. Для произвольного целого числа существует циклическая группа порядка

Доказательство. Рассмотрим группу из утверждения 2.8. Легко убедиться в том, что порождается элементом [1], а следовательно, является циклической. Группа, рассмотренная в задаче 2.6, есть не что иное, как частный случай группы при Заметим, что элемент 1 является не единственным элементом, порождающим эту группу. В частности, группа может быть порождена также элементом 5 (см. задачу 2.9). Такие элементы, порождающие группу, называются порождающими элементами.

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

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

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

то является гомоморфным отображением Следовательно, изоморфны.

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

Утверждение 2.12. Все конечные группы, порядок которых является простым числом, циклические.

Доказательство следует из утверждения 2.2.

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

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

Утверждение 2.14. Пусть соответственно порядки элементов группы Если и то в существует элемент порядка

Доказательство. Предположим сначала, что что числа тип взаимно простые. В этом случае элемент является искомым. В самом деле, поскольку то порядок I элемента делит . С другой стороны, поскольку то Аналогично Однако, поскольку получаем, что а следовательно, Отсюда и из того, что имеем Рассмотрим случай, когда Разлагая числа на простые множители и упорядочивая последние специальным образом, получаем

где

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

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

N.1. Для произвольного целого числа а и произвольного целого положительного числа существуют такие числа что

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

N.4. Алгоритм Евклида. Этот алгоритм хорошо известен как алгоритм нахождения наибольшего общего делителя.

Предположим, что и рассмотрим следующую последовательность равенств:

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

Согласно свойствам целых чисел,

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

N.5. Для любых двух целых чисел существуют такие целые числа х и у, что

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

Свойство можно также сформулировать в следующем виде:

N.5. Если числа взаимно простые, то существуют такие целые числа что

Доказательство. Так как то Так как взаимно простые, то

Функция Эйлера определяется для всех натуральных как количество чисел между взаимно простых с Положим Если где простое число, то среди всех целых чисел от 1 до содержится чисел, кратных Отсюда следует, что

В общем случае, когда простые числа), имеем [4]

Доказательство последнего равенства здесь опускается.