«Содержание этой книги составляет годовой курс Алгебраические коды, который автор читал в течение ряда лет в Московском физико-техническом институте (государственном университете). Разумеется, за 120-130 академических ...»

Введение в алгебраические

коды

Сагалович Ю.Л.

4 октября 2011 г.

Предисловие

Содержание этой книги составляет годовой курс "Алгебраические коды", который автор читал в течение ряда лет в Московском физико-техническом институте (государственном университете). Разумеется, за 120-130 академических часов, включая и семинарские занятия, можно сообщить студентам лишь

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

Тем более автор был поставлен в тупик, когда ему порекомендовали написать для студентов учебное пособие под названием "Алгебраические коды". Можно ли согласиться на такой шаг, когда мировое сообщество специалистов и исследователей имеет в своем распоряжении книги У.У. Питерсона; В.Д. Колесника и Е.Т. Мирончикова; Э. Берлекэмпа; Э.Л. Блоха и В.В. Зяблова; У.У. Питерсона и Уэлдона; Т. Касами, Н. Токура, Ё. Ивадари и Я. Инагаки; Ф. Дж. Мак-Вильямс и Н.Дж.А. Слоэна; Э.М. Габидулина и В.Б. Афанасьева; Р. Блэйхута; Лидла и Нидеррейтера.

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

В то же время в данную книжку включена специальная глава "Начальные сведения из теории чисел", хотя в перечисленных выше источниках теоретико-числовые сведения использованы, но разрозненно.

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

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

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

Такой уровень был выдающимся достижением тридцать лет тому назад, когда вышла в свет книга Ф. Дж. Мак-Вильямс и Н. Дж. А. Слоэна. Теперь другое время, и когда накоплен огромный запас методов построения кодов, удовлетворяющих разнообразным практическим нуждам, когда необычайным образом разрастается тематика исследований по теории кодирования, когда специалистам, овладевшим началами теории кодов, предоставлен широкий ассортимент способов построения реальных систем связи, назревает другая необходимость. Это — необходимость подняться в преподавании теории кодирования на новый уровень абстракции. Возможность к такому переходу обеспечена появлением монографии "Алгеброгеометрические коды (Основные понятия)" трех авторов: С.Г. Вледуца, Д.Ю. Ногина и М.А. Цфасмана. На мой взгляд, сформирована Предисловие и аудитория молодых людей с хорошей математической подготовкой, способная к восприятию новых серьезных сведений.

Данная же книжка преследует куда более скромную цель:

помочь читателю освоить основы теории алгебраических кодов и более или менее осмысленно ориентироваться в обширной литературе по теории кодирования.

Автор искренне благодарит В.Б. Афанасьева и В.В. Зяблова за труд первого чтения, сопровождавшегося рядом важных советов и замечаний, которые послужили улучшению предлагаемой книги, Д.С. Осипова и Д.В. Лаконцева за помощь в оформлении оригинала-макета, В.С. Козякина за неоценимое содействие и помощь.

Предисловие ко второму изданию В настоящем издании прежде всего устранены недочёты предыдущего издания; улучшено изложение в нескольких местах книги; внесены незначительные изменения в списки задач к главам; существенно расширена глава с указаниями к решению задач. Внесены дополнения в главу о конечных полях В теоретикочисловую главу помещен раздел об алгоритме Эвклида отыскания наибольшего общего делителя двух целых чисел. Это вызвано тем, что в разделах 7.7 — 7.10, написанных при участии В.Б.Афанасьева, подробно изложен метод декодирования, основанный на алгоритме Эвклида. Среди других методов этому методу отдано предпочтение по той причине, что алгоритм Эвклида, известный с незапямятных времён, через столетия оказался как будто специально приспособленным для весьма специфических нужд теории кодирования.

Введение 0.1. Система передачи информации.

Двоичный симметричный канал В простейшем случае система передачи сообщений состоит из передатчика, канала связи, и приемника. Схематически он выглядит, как показано на рис. П а П а П Ка а Рис. 1. Простейшая система передачи информации Передатчик передает сообщения в виде последовательностей одинаковой длины n, состоящих из нулей и единиц:

(0.1.1) u = (u1, u2,..., un ), ui = 0, 1.

(Вообще говоря, последовательности могут иметь и разные длины, но здесь этот случай рассматриваться не будет.) В канале действует случайная помеха: каждый символ передаваемой последовательности независимо от других может быть искажен с вероятностью (0.1.2) < 1/2.

Это означает, что с вероятностью < 1/2 происходят переходы 0 1, 1 0 и с вероятностью = 1 компоненты 0 и 1 последовательности u сохраняют свое значение. Такой канал называется двоичным симметричным. Схематически он изображен на рис. 2.

Часто вместо "последовательности" применяют термины "слово" или "вектор". Для нас это синонимы, но для определенности и единообразия в дальнейшем употребляется термин "вектор".

Процесс действия помехи на передаваемый вектор можно описать следующим образом. Введем в рассмотрение вектор где ei = 1, если символ ui искажен, и ei = 0 — в противном случае. Вектор (0.1.3) называется вектором-ошибкой.

Пусть передавался вектор u = (110001001), а на приемном конце получен вектор v = (010001101). Это означает, что в канале подверглись искажению первый и седьмой символы передававшегося вектора. Это означает, что в векторе e единицы расположены на первом и седьмом местах, т.е. e = (100000100).

Легко заметить, что вектор v получается поразрядным сложением векторов u и e по модулю два: 0+0=1+1=0, 0+1=1+0=1.

Вообще, если передается вектор (0.1.1), то на приёмном конце получают вектор Про такой канал говорят, что это канал с "аддитивной помехой".

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

"повторить передачу", а значит, правильным считать тот символ, который встречается чаще. И чем больше повторять передачу, тем надежнее она будет. Такая уверенность основана на том, что в силу условия (0.1.2) правильных значений передаваемого символа окажется больше, чем неправильных.

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

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

Положим в общем случае, что ради надежной передачи информации, вместо k символов приходится передавать n > k символов. Сопоставление некоторым способом n символов заданным k символам вектора называют кодированием. Отношение k/n называется скоростью передачи. В предыдущем случае k = 1, и скорость передачи k/n = 1/n.

Восстановление закодированных k символов по n переданным символам, каждый из которых мог подвергнуться искажению с вероятностью (0.1.2), называется декодированием. Не исключена возможность, что это декодирование окажется ошибочным.

Теперь систему передачи информации можно детализировать более подробно, как показано на рис. 3. Из источника сообщений извлекается вектор длины k, кодер преобразует его в вектор длины n, который передается по каналу связи с помехой, а затем декодируется и поступает по назначению.

Альтернативу методу многократного повторения доставляет знаменитая теорема Шеннона.

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

Достоверность передачи измеряется вероятностью P ошибки декодирования.

Основную роль в точном формулировании теоремы Шеннона играет функция энтропии H(x). Она имеет вид Если не оговорено иное, логарифмы берутся при основании 2. Натуральный и десятичный логарифмы, как обычно, пишутся соответственно ln и lg. Если же логарифмы берутся при некотором основании q, то пользуются обозначением Hq (x). Последнее имеет место в случае так называемого q-ичного канала, который будет обсуждаться в одной из следующих глав.

С помощью функции энтропии определяется упомянутая пропускная способность C( ) канала, представленного на рис. 2.

Она зависит только от величины – вероятности искажения одного двоичного символа.

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

Каково бы ни было > 0, при достаточно большом n, и k/n < C( ) = 1 H( ), существует такое кодирование, при котором P <.

Теорема Шеннона доказана методом случайного выбора векторов и не говорит, как реализовать такое кодирование. Однако, если доказано существование "хорошего" кодирования, то это прямой сигнал к поиску конструктивных методов создания кодов с заданными свойствами. Значительная часть книги посвящена именно этой теме.

0.2. Кодовое расстояние Важнейшую роль в теории кодирования играет понятие кодового расстояния. Под кодовым расстоянием чаще всего подразумевают так называемое расстояние Хэмминга. Расстоянием d(a, b) между двумя векторами a = (a0, a1,..., an1 ) и b = (b0, b1,..., bn1 ) называется число таких компонент i двух векторов, в которых последние не совпадают, т.е., в которых ai = Нетрудно показать, что так определенное расстояние обладает всеми свойствами метрики. Действительно, очевидно, что расстояние симметрично: d(a, b) = d(b, a). Выполняется также неравенство треугольника. В самом деле, расположим три вектора a, b, c в виде таблицы, обозначив в ней числами m1 0, m2 0, m3 0, m4 0, m5 0, m6 0 количество столбцов соответственно Тогда Отсюда получаем d(a, b) + d(a, c) d(b, c) = 2(m3 + m4 ) 0, что и требовалось.

Пусть в нашем распоряжении имеется некоторое множество A двоичных векторов длины n, и число |A| векторов этого множества удовлетворяет условию |A| = M. Назовем это множество кодом. Положим a, b A, d = mina=b d(a, b), и минимум Столбцы (111)T, (000)T отсутствуют, так как никакого вклада в расстояние не вносят.

берется по всем CM парам векторов множества A. Эта величина носит название "минимальное расстояние кода" или "кодовое расстояние". Оба термина — синонимы.

Пусть минимальное расстояние кода есть d = 2t + 1. Если при передаче вектора a было искажено t, или менее символов, то принятый вектор a будет a = a + e, где вектор-ошибка e содержит t или менее единиц. Тогда для произвольного вектора x A, x = a, будет справедливо неравенство d(a, a) < d(a, x).

Оно означает, что принятый вектор a ближе к передававшемуся вектору a, чем к любому другому вектору x A, x = a.

Так как в силу (0.1.2) вероятность того, что произошло меньшее число ошибок, больше, чем вероятность того, что произошло большее число ошибок 2, то декодирование принятого вектора a в вектор a будет правильным. Такой способ декодирования является частным случаем декодирования "по максимуму правдоподобия", который независимо от способа его реализации в своей расширительной трактовке преследует цель минимизировать ошибку декодирования.

В этом месте и проявляется теорема Шеннона.

"Правильное декодирование" есть синоним выражения "исправлена ошибка". Сказанное означает, что справедливо Утверждение 0.2.1. При код A исправляет все независимые ошибки кратности t и менее.

Пусть цель исправления ошибок не преследуется, а требуется только установить факт наличия ошибок. Ясно, что при d = 2t + 1 никакие независимые ошибки кратности 2t и менее не могут преобразовать передававшийся вектор a ни в один из векторов x A, x = a. Установление факта наличия ошибок называют "обнаружением" ошибок или "отказом от декодирования".

Таким образом, имеет место Утверждение 0.2.2. При d 2t + 1 код A исправляет все независимые ошибки кратности t и менее, или обнаруживает все независимые ошибки кратности 2t и менее.

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

Пусть, наконец, кодовое расстояние четно: d = 2t + 2. Разумеется, по-прежнему исправляются все независимые ошибки кратности t и менее. Но если произойдет t+1 ошибок, то исправить их невозможно, зато можно обнаружить, так как они не смогут преобразовать ни один вектор a A ни в один вектор Иначе говоря, справедливо Утверждение 0.2.3. При d 2t + 2 код A исправляет все независимые ошибки кратности t и менее, и одновременно обнаруживает все независимые ошибки кратности t + 1.

Изложенному здесь можно придать геометрическую форму.

Рассмотрим рис. 4 и 5.

Если был передан вектор a (или b), и произошла одна ошибка, то будет принят вектор a или ((b )). В случае расстояния d = 3 принятый вектор a будет действительно ближе к истинно переданному a, а принятый вектор b будет действительно ближе к истинно переданному b. Декодирование будет безошибочным. Если произойдут две ошибки, то при расстоянии d = принятый вектор a совпадет с вектором b, а принятый вектор b совпадет с вектором a. Декодирование будет ошибочным.

В случае расстояния d = 4 при двух ошибках оба передававшихся вектора a и b превратятся в вектор c, который одинаково удален от a и b, и не будет декодирован ни в один из них. Обнаружен факт наличия ошибок. В принятой терминологии — "обнаружена ошибка".

0.3. Скорость передачи и минимальное расстояние Интуитивно ясно, что создание расстояния между кодовыми векторами кода A с необходимостью влечет увеличение длины вектора, и как отмечалось выше, ведет к уменьшению скорости передачи k/n. Поэтому интересно выяснить, каков закон, связывающий скорость передачи кода с кодовым расстоянием.

Будем выводить этот закон так называемым методом исчерпания, одновременно строя сам код A, содержащий M векторов длины n, находящихся на расстоянии не менее чем d друг от друга. Заметим при этом, что k =] log2 M [.

В качестве первого вектора u1 выберем произвольный вектор из 2n всех векторов длины n. Затем найдем все векторы, которые находятся на расстоянии 1, 2,..., d 1 от него. Вместе с вектором u1 их будет всего Удалим эти векторы из нашего арсенала выбора. Оставшиеся векторов находятся от вектора u1 на расстоянии, не меньшем, чем d. Поэтому любой из них может быть выбран как вектор u2 нашего кода. И в этом случае найдем все векторы, которые находятся на расстоянии 1, 2,..., d 1 теперь уже от вектора u2. По построению они находятся на расстоянии, не меньшем, чем d и от вектора u1.

Удалим и эти векторы из нашего арсенала выбора, не обращая внимания на то, что некоторые из них были удалены ранее. Оставшиеся не менее чем векторов находятся от векторов u1 и u2 на расстоянии, не меньшем, чем d. Любой из них может быть выбран как вектор u3.

Поступая с ним так же, как и с предыдущими, а затем выбирая последовательно векторы кода до вектора uM 1, удалим всего векторов. Если количество оставшихся векторов будет удовлетворять неравенству то можно выбрать еще один вектор, который находится на расстоянии, не меньшем, чем d от всех предыдущих, а это означает, что код A с параметрами n, d, M заведомо существует.

Заметим, что множество d1 Cn векторов, отстоящих на расстоянии не менее, чем d 1 от вектора ui, вместе с самим вектором ui называется шаром радиуса d 1, а вектор ui — его центром.

Неравенству (0.3.5), как легко видеть, можно придать иную форму:

Читается это неравенство так: если скорость передачи k/n кода удовлетворяет неравенству (0.3.6), то код длины n с расстоянием d существует. Неравенство (0.3.6) называется границей Гилберта. Оба последних неравенства выражают типичную границу существования. Способ ее вывода — исчерпание — основан на переборе всех 2n векторов длины n, ничего общего не имеет с алгеброй, и ни в коем случае не может быть способом построения кода. Довольно грубое обращение с шарами, которые могут пересекаться, и потому один и тот же вектор может удаляться не один раз, создает впечатление о возможности улучшения границы существования. Разумеется, учитывая возможность многократного выбрасывания каких-нибудь векторов, в неравенстве (0.3.6) можно получить величину, меньшую, чем та, которая стоит под знаком суммы. Но когда говорят об улучшении границы, имеют в виду асимптотическую форму границы (см. 8.3). Так вот ее-то, как показала история, улучшить не удается.

Создание расстояния d между векторами играет важную роль не только в случае помех, свойственных двоичному симметричному каналу, показанному на рис. 2. На рис. 6 показан так называемый двоичный стирающий канал.

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

Тривиальным методом исправления l стираний является подстановка на (известные!) стертые позиции всех возможных 2l комбинаций из нулей и единиц и выбор из них единственной правильной комбинации, которая заведомо существует. Имеет место Утверждение 0.3.1. Для исправления любых l стираний необходимо и достаточно чтобы, минимальное расстояние кода удовлетворяло условию Д о к а з а т е л ь с т в о. Пусть выполняется условие d l + 1. Заменим все t стертых символов всеми возможными 2l способами символами 0 и 1. Тогда одна и только одна комбинация l нулей и единиц восстановит принятый вектор в вектор переданный. Но любая другая ошибочная замена будет обнаружена, так как она будет находиться на расстоянии не более, чем d 1 от истинной. Наоборот, при d < l + 1 найдется такая ошибочная замена, которая не будет обнаружена, и произойдет ошибка декодирования.

Можно воспользоваться таким рассуждением. Пусть принятый вектор a содержит l d1 стираний, и пусть код A имеет минимальное расстояние d. Такой код содержит в точности один вектор u, совпадающий с принятым вектором a в неискажённой его части. Действительно, если найдётся ещё один вектор v с таким свойством, то окажется, что d(u, v) = l d 1 < d, что противоречит условию.

Рассмотрим случай, когда в канале при передаче могут возникнуть искажения обоих видов, т.е. одновременно, ошибки и стирания. Имеет место Утверждение 0.3.2. Для исправления любых t независимых ошибок и одновременно любых l (независимых) стираний необходимо и достаточно чтобы, минимальное расстояние кода удовлетворяло условию Д о к а з а т е л ь с т в о. Пусть в принятом векторе a, кроме t ошибок, имеется l стёртых символов. Удалим из вектора a, равно как и из всех остальных векторов кода A все те компоненты, в которых размещены стирания вектора a. Получится новый код A с параметрами n = n l, d d l. Этот код исправляет любые независимые ошибки кратности t [(d l 1)/2] и менее. Когда ошибки будут исправлены, мы возвратимся к коду A, которому принадлежит принятый вектор a содержащий теперь уже только стирания. Их мы умеем исправлять, применяя предыдущие соображения.

Сравним три знакомых нам соотношения (0.3.8),(0.2.4), (0.3.7) Второе получается из первого, если есть только ошибки, и нет стираний, а третье получается из первого, если есть только стирания, и нет ошибок.

Иными словами, если минимальное расстояние кода есть d, то при отсутствии стираний код исправляет любые t (d1)/ независимых ошибок, а при отсутствии ошибок исправляет любые l d 1 стираний. Наконец, при наличии не более чем l стираний код с расстоянием d исправляет любые t [(d l 1)/2] или менее независимых ошибок. Исправление стираний будет обсуждаться также в гл. 6.

0.4. Код Хэмминга Рассмотрим матрицу Все семь столбцов матрицы различны, и из всех возможных восьми столбцов длины 3 отсутствует нулевой столбец.

Пусть код A состоит из всех таких векторов, скалярное произведение которых на каждый из трех векторов-строк (0111100) = z1, (1110010) = z2, (1101001) = z матрицы H равно нулю. Этому условию удовлетворяет, например, вектор u = (1000011) :

На самом деле (0.4.10) изображает операцию uH T = 0, т.е.

умножение вектора u на матрицу H T, где индекс T означает транспонирование.

Положим, что при передаче вектора u данного примера произошла одиночная ошибка, например, в четвертом разряде вектора, и на приемном конце принят вектор v = u + e = (1000011) + (0001000) = (1001011). Тогда, выполнив на приемном конце умножение принятого вектора на транспонированную матрицу H, получим а это есть четвертый слева столбец матрицы H. Его номер указывает на то, что при передаче был искажен четвертый символ Когда ниже в тексте будет введён в обращение qичный, а не только двоичный, канал, читатель поймёт, что предыдущие рассуждения об исправлении ошибок и стираний, а также обнаружении ошибок, останутся справедливыми.

кодового вектора. Вектор-ошибка при умножении принятого вектора v на транспонированную матрицу H "вырезал" именно тот столбец матрицы, номер которого указывает на номер искаженного символа кодового вектора.

Изменим теперь слегка матрицу (0.4.9), расположив ее столбцы в лексикографическом порядке.

Примечательной чертой такого нового расположения столбцов является то, что при любой одиночной ошибке в принятом векторе v результатом умножения vH T будет в точности двоичный номер искаженного разряда кодового вектора. В общем случае матрица H содержит m строк и n = 2m 1 ненулевых столбцов, которые все различны. Код A, все векторы которого, умноженные скалярно на строки матрицы H, дают нуль, называется кодом Хэмминга. Он содержит 22 1m кодовых векторов, его кодовое расстояние равно трем, он исправляет все одиночные ошибки, или обнаруживает все двойные независимые ошибки.

Подробнее этот код будет обсуждаться в главе 4.

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

Предварительно зададимся вопросом: нельзя ли, все-таки, для повышения надежности передачи сообщений обойтись иными средствами, а не алгебраическими? Быть может, стоит всегонавсего увеличить энергию сигнала — и помеха будет подавлена. Порой это сделать нельзя из-за дефицита энергии, но даже и при избытке таковой обойтись без средств кодирования, в том числе и алгебраического, бывает невозможно. Например, при использовании спутниковой связи, когда неизбежна концентрация нескольких каналов связи в одной точке, усиление энергии сигнала может привести к взаимному влиянию каналов и наведению помех одним каналом в другом.

0.5. Задачи к введению 0.1. Доказать утверждение: для того, чтобы код исправлял любые комбинации t или менее ошибок, и одновременно обнаруживал все комбинации t t или менее ошибок, необходимо и достаточно, чтобы кодовое расстояние d удовлетворяло условию d t + t. 0.2. Доказать, что код Хэмминга исправляет любые два или менее стираний.

Глава 1.

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

Опыт показал однако, что безусловная красота теории чисел увлекает молодых людей и побуждает их к расширеннию теоретико-числовых знаний. На первый случай им можно порекомендовать такие источники, как "Основы теории чисел" И.М. Виноградова и "Теория чисел" А.А. Бухштаба.

Итак, считаются известными понятия:

наибольшего общего делителя и наименьшего общего кратного двух чисел a и b. Между ними имеется связь Каноническое разложение числа a на сомножители имеет вид где pi – простое число, i — натуральное, и это разложение единственно.

Простых чисел бесконечно много. Действительно, если найдены все первые k простых чисел до pk включительно, то число либо само будет простым, либо любой простой его делитель, деля всю сумму, не будет совпадать ни с одним из чисел (1.1.1).

1.2. Наибольший общий делитель. Алгоритм Эвклида Разумеется, для определения общего наибольшего делителя двух целых чисел a и b, a > b можно воспользоваться их каноническими разложениями и выделить их максимальную общую часть. Однако для этой цели существует замечательное средство — алгоритм Эвклида. В теории чисел и алгебре алгоритм Эвклида имеет дело только с вычислением наибольшего общего делителя d = (a, b) двух чисел a и b. Именно, в чистом виде Д о к а з а т е л ь с т в о. Пусть x пробегает приведённую систему вычетов, т.е.

Тогда ax1 также пробегает приведённую систему вычетов, быть может, в другом порядке:

Сравнения можно почленно перемножать Если ri и i принадлежат наименьшим неотрицательным вычетам, а это всегда можно сделать, то обе части сравнения можc c простое с модулем, откуда что и требовалось.

Отсюда следует Теорема 1.8.2 (Ферма). При простом p, и a, не делящемся на p, Сравнение верно при всех a, так как оно верно и при a, делящемся на p.

Стоит показать, что это сравнение справедливо и при a, не делящемся на p. Действительно, из теоремы Ферма получаем (см. утверждение 1.3.1) ap1 = tp+1, ap = atp+a = T p+a, ap a(modp).

1.9. Мультипликативность функции Эйлера Теорема 1.9.1. Если (a, b) = 1, то (ab) = (a)(b).

Доказательству теоремы предпошлем следующую лемму:

Лемма 1.9.2. Сумма принимает все значения из привeденной системы вычетов по модулю ab тогда и только тогда, когда x пробегает приведенную систему вычетов по модулю b, а y пробегает приведенную систему вычетов по модулю a.

Д о к а з а т е л ь с т в о. Достаточность Легко видеть, что Действительно, (ax, b) = 1 по условию, а b|by. Поэтому (ax + by, b) = 1. (В противном случае, т.е. если (ax + by, b) = d > 1, то d|(ax + by), d|b. Отсюда d|by, а значит, d|(ax + by by), т.е, d|ax, что противоречит тому, что (ax, b) = 1.) Из соображений симметрии также (ax + by, a) = 1. Отсюда следует (1.9.19).

Необходимость. Если в сумме (1.9.18) хотя бы одно x (или также y) не принадлежит приведенной системе вычетов по модулю b, (по модулю a,), то такая сумма не принадлежит приведенной системе вычетов по модулю ab. Действительно, пусть, например, (x, b) = d > 1. Тогда d делит оба слагаемые в (1.9.18), и, следовательно, сумма (1.9.18) не взаимно проста с ab.

Лемма доказана.

Следствие 1.9.3. Сумма (1.9.18) не взаимно проста с ab тогда и только тогда, когда хотя бы одно x (или также y) не принадлежит приведенной системе вычетов по модулю b, (по модулю a,) Теперь из полной системы вычетов по модулю ab удалим все Z вычетов, не взаимно простых с ab. Останутся ab Z = (ab) вычетов, взаимно простых с ab и только они. Из общего числа ab сумм ax + by удалим те из них, в которых выполняется хотя бы одно из соотношений (x, b) = 1, (y, a) = 1. Их будет ровно столько же, т.е. Z. Оставшихся ab Z сумм будет в точности (a)(b).

Таким образом, произведение (a)(b) и число (ab) выражают одну и ту же величину, а потому (ab) = (a)(b), и теорема доказана.

Приведём другое доказательство теоремы 1.9.1.

Для этого рассмотрим таблицу На основании теоремы 1.6.2 числа каждого столбца пробегают полную систему вычетов по модулю a, и, таким образом, в каждом столбце содержится в точности (a) чисел, взаимно простых с a. Каждый столбец имеет вид Числа, взаимно простые с b содержатся в тех и только в тех столбцах, в которых (b, r) = 1. Это означает, что во всех (b) столбцах (1.9.21), где (b, r) = 1, и толко в них содержится (a)(b) чисел, взаимно простых одновременно и с a и с b, а значит, и с их произведением ab. Но всего в таблице (1.9.20) содержится (ab) таких чисел. Отсюда (ab) = (a)(b), что и требоваось.

1.10. Вычисление функции Эйлера Теорема 1.10.1. Пусть где числа простые и попарно различные. Тогда взаимно просты, то cогласно теореме 1.9. Действительно, среди pi чисел 1, 2,..., pi ровно pi 1 чисел делится на pi. Остальные чисел не делятся на pi, а значит, взаимно просты с ним и с pi. i Отсюда и из (1.10.23) получается (1.10.22).

1). a = 1000 = 23 53, (1000) = 1000(1 1/2)(1 1/5) = 400;

2). a = 255 = 3 · 5 · 17, (255) = 255(1 1/3)(1 1/5)( 1/17) = 128;

3). a = 13068 = 4 · 27 · 121 = 22 33 112, (13068) = 13068( 1/2)(1 1/3)(1 1/11) = (1/2)(2/3)(10/11) = 1980;

4). a = 1001 = 7 · 11 · 13, (1001) = 6 · 10 · 12 = 720.

Если бы перед выводом теоремы Эйлера была предложена, например, задача — найти остаток от деления числа 729720 на 1001 — она могла вызвать недоумение. На самом деле 1001 = = 7 · 11 · 13, (1001) = 720, (729, 1001) = 1, 729720 1(mod 1001).

1.11. Первообразные корни При (a, m) = 1 существуют положительные целые числа с условием Например, (теорема Эйлера) Определение 1.11.1. Наименьшее из чисел, удовлетворяющее (1.11.24) называется показателем, которому a принадлежит по модулю m.

Таким образом, 4 – есть показатель, которому 2 принадлежит по модулю 5, (5) = 4.

В то же время Таким образом, число 2 – есть показатель, которому 5 принадлежит по модулю 12, хотя (12) = 4. Более того, все элементы приведённой системы вычетов по модулю 12 принадлежат показателю 2.

Утверждение 1.11.2. Если a по модулю m принадлежит показателю, то числа 1 = a0, a,..., a1 попарно несравнимы по модулю m.

Действительно, из сравнения al ak (modm), (0 k < l < ) следовало бы alk 1(modm), (0 l k < ), что противоречит определению величины : ведь есть наименьшее из чисел, для которых a 1(modm).

Утверждение 1.11.3. Если a по модулю m принадлежит показателю, то a1 a2 ( mod m) тогда и только тогда, когда 1 2 (mod), т.е. 1 2 = t.

Сначала перед доказательством приведем Таким образом, число 2 принадлежит показателю = 4 по модулю 15.

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

Доказательству предпошлем следующее построение. Пусть r1 и r2 – наименьшие неотрицательные вычеты по модулю ; r1 <, r2 <, тогда при некоторых q1 и q2 имеем 1 = q1 + r1, 2 = q2 + r2. Отсюда и из сравнения a 1(modm) получаем a1 = (a )q1 ar1 ar1 (modm), a2 = (a )q2 ar2 ar2 (modm).

a2 (modm).

Тогда ar1 ar2 (modm), и в силу утверждения 1.11.2 r1 = r2 = r, (так как в противном случае ar1 и ar2 были бы несравнимы), а потому 1 = q1 + r, 2 = q2 + r, т.е. 1 2 (mod).

Достаточность. Пусть 1 2 (mod). Тогда r1 = r2, и из (1.11.25) получаем, что a1 a2 (modm). Теорема доказана.

Имеем далее т.е.

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

Определение 1.11.5. Числа, принадлежащие показателю (m), называются первообразными корнями по модулю m, (если они существуют).

Иначе говоря, a будет первообразным корнем по модулю m, когда ни при каком < (m) не выполняется сравнение Все случаи, когда существуют первообразные корни по модулю m, суть Доказательство этого факта здесь опущено. Читатель найдёт его в руководствах по теории чисел.

Утверждение 1.11.6. В приведенной системе вычетов по модулю m количество чисел, принадлежащих показателю, есть (.) Действительно, покажем, что если a принадлежит показателю по модулю m, и (, ) = 1, то a также принадлежит показателю по модулю m.

Предположим противное, т.е., что (a )1 1(modm), где 1 <. Тогда, согласно утверждению 1.11.3, 1 0(mod). В свою очередь это означает, что 1 делится на, что противоречит условию 1 <, а потому 1 =, что и требовалось.

Пусть теперь (, ) = d > 1. Положим /d = 1 <. Тогда )1 = (a ) d = (a ) d = 1. Это означает, что a принадлежит показателю 1 < по модулю m.

В частности, из утверждения 1.11.6 следует, что число первообразных корней есть Пусть c = (m), и q1, q2,..., qk – различные простые делители числа c.

Утверждение 1.11.7. Для того, чтобы g, взаимнопростое с m, было первообразным корнем по модулю m, необходимо и достаточно, чтобы g не удовлетворяло ни одному из сравнений g qi 1(modm).

Д о к а з а т е л ь с т в о. Необходимость. Если то c = (m) не показатель, которому принадлежит g по модулю Достаточность. Пусть не выполняется ни одно из сравc нений g qi 1(modm), и пусть показатель < c. Тогда c/ – целое, и пусть c/ = qt, c/q = t, g t = (g )t 1 mod m. Это значит, g c/q 1 mod m, что противоречит условию.

Более простое доказательство этого факта получается из элементарных сведений о циклических группах (см. след. гл.) 1.12. Индексы Пусть p простое нечетное, n 1, m – одно из чисел 2, 4, p, 2pn и пусть c = (m).

Пусть g — первообразный корень по модулю m. Заметим, что (g, m) = 1, так как g принадлежит приведенной системе вычетов по модулю m.

Утверждение 1.12.1. Если пробегает полную систему наименьших неотрицательных вычетов = 0, 1,..., c 1 по модулю c, то g пробегает приведенную систему вычетов по модулю m.

Д о к а з а т е л ь с т в о. g пробегает c чисел взаимнопростых с m, так как (g, m) = 1. Остается применить утверждение 1.11.2.

Определение 1.12.2. Пусть (a, m) = 1. Если a g (mod m), то называется индексом числа a по модулю m при основании g и обозначается Ввиду утверждения 1.12.1 всякое такое a, что (a, m) = 1, имеет единственный индекс 0 среди чисел = 0, 1,..., c 1.

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

Из определения индекса следует, что числа с одинаковым индексом образуют класс вычетов по модулю m, так как два числа, сравнимые с третьим, сравнимы между собой. (Сравнимые числа принадлежат к одному классу.) Зная 0, можно указать все индексы числа a :

тогда и только тогда, когда Утверждение 1.12.3. Имеет место следующее сравнение:

Действительно, a g ind a (modm), b g ind b (modm),..., l g ind l (modm).

Сравнения можно почленно перемножать, поэтому:

ab · · · l g ind a+ind b+···+ind l.

Следовательно, ind a+ind b+...+ind l есть один из индексов произведения ab · · · l Аналогия с логарифмами очевидна.

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

Ривеста, А. Шамира и Л. Адлмана.

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

И криптографу и криптоаналитику известно следующее:

Модуль N и такое число e, что e, ((N ), e) = 1. Это так называемый открытый ключ, содержащийся в справочнике, который можно купить в газетном киоске.

Разложение N = P Q, где P, Q — простые числа, это закрытый, секретный ключ.

Он известен только криптографам, но неизвестен криптоаналитикам. Утверждение, что разложение N = P Q, может быть кому-то неизвестным, на первый взгляд кажется нелепым. Кто не знает, как разложить число на множители!? Однако именно в этом утверждении заключен весь корень прочности системы защиты.

Шифрование происходит следующим образом:

Пусть следует передать число M. В действительности передается Так как (e, (N )) = 1, то легко заранее найти такое x, что e x 1(mod(N )).

В самом деле, на основании теоремы 1.7.2 в разделе 1.7 имеем:

В лекциях завершение доказательства теоремы Эйлера всякий раз производило впечатление неожиданностью результата, появлявшегося после довольно скучного рассказа о свойствах сравнений. Простота и изящество теоремы, казалось, придавали ей очевидную эстетическую значимость, усомниться в которой было невозможно. Но однажды лектор был обескуражен вопросом: "А каково практическое значение этой теоремы?" С тех пор теорема Эйлера непременно сопровождалась рассказом о ее криптографической ценности. Потенциальный критик теоремы переходил в ряды ее почитателей, ибо ничто так не утверждает человека в собственной значимости (а заодно и значимости теоремы), как сознание приобщенности к секретам.

Если при (a, m) = 1 элемент x пробегает приведенную систему вычетов по модулю m, то и ax пробегает приведенную систему вычетов.

Здесь m = (N ), a = e. Для отыскания x можно с успехом воспользоваться равенством (1.2.4), применив для этого процедуру раздела 1.2. В (1.2.4) следует положить a = e, b = (N ), d = 1. Тогда s = x.

Из e x 1(mod(N )) на основании (1.3.16) следует e x = y(N ) + 1, где y целое.

Дешифрование:

Получив C M e (modN ), поступают следующим образом:

C x M ex (modN ) M y(N )+1 (modN ) (M (N ) )y M (modN ).

Существуют две возможности.

В этом случае так как в силу (1.13.26) Отсюда C x M (modN ), и на основании (1.3.16) C x = M + uN. Поэтому в силу (1.13.26) немедленно получается u = 0, C x = Так как N = P Q и P, Q простые числа, то вследствие (1.13.27) число M может быть кратным только одного из чисел P, Q. В самом общем случае можно считать M = P t L, L < Q, (L, N ) = = 1, t – натуральное число. Имеем M ex = P tex Lex P t(y(N )+1) Ly(N )+1 (modN ). (1.13.28) Рассмотрим множители в левой части сравнения (1.13.28) раздельно.

В силу условия (L, N ) = Далее, зная, что положим Если сравнение имеет место по модулю m, (см. утвержд.

1.5.4), то оно имеет место и по модулю d, равному любому делителю числа m.

С другой стороны, так как (P, Q) = 1, то по теореме Ферма и потому Из (1.13.30), (1.13.31) в силу утверждения 1.4.1 следует Тривиальным образом Если сравнение имеет место по нескольким модулям (см. утвер.

1.5.3) то оно имеет место и по модулю, равному наименьшему общему кратному модулей, т.е.

Из (1.13.28), (1.13.29) и (1.13.32) получаем окончательно Это означает, что Как и выше, ввиду M < N, v = 0, C x = P t L = M.

Центральную роль в вычислениях играет равенство При очень больших и почти равных P, Q найти разложение N = P Q — весьма трудоемкая операция, что и лежит в основе надежды на длительность взлома системы защиты криптоаналитиком. (Попытку взлома называют атакой).

(P 1)(Q 1) = 16 30 = 480. Пусть e = 7, (7, 480) = 1.

Отсюда x = 343.

Действительно, из ex = y(N )+1 следует 7x = 480y +1 = (68 7 + 4)y + 1. Отсюда (4y + 1)/7 целое, т.е. 4y + 1 = 7z.

Отсюда y = (7z 1)/4 целое, т.е. 3z 1 = 4v.

Отсюда z = (4v + 1)/3 целое, т.е. v + 1 = 3, и v = 2. Далее 3z = 8+1, z = 3, 4y +1 = 21, y = 5, 7x = 4805+1 = 2401, x = 343, что и требовалось.

Положим M = 5. Тогда C = 57 129(mod527.) Получив в виде сообщения число 129, мы должны извлечь из него корень седьмой степени по mod527.

Согласно вышесказанному, C x = 129343 (mod527.) 1292 = 16641 = 52731+304, и 343 = 256+64+16+4+2+ 129343 = 129256 12964 12916 1294 1292 30432 3048 3042 2224 222222191304129 2733 273 222 191 304 129 5(mod527), что и требовалось.

Подчеркнем, что не зная (N ), криптоаналитик не может вычислить x. Знание (N ) требует знания разложения N = P Q, и получение этого разложения — самая трудоемкая процедура. Объем L(N ) вычислений для разложения N = P Q Обычно N не менее, чем семисот-, а то и тысячезначное число. Прямая и обратная функции, т.е., с одной стороны, вычисление C M e (modN ), а с другой — получение C x (modN ), где главную роль играет отыскание неизвестного криптоаналитику разложения N = P Q, по трудоемкости — несоизмеримы.

Такие функции принято называть односторонними.

Не доказана неизбежность знания разложения N = P Q.

Можно ли избрать другой путь дешифрования, не использующий соотношение (N ) = (P )(Q)?

1.14. Задачи к главе 1.1. Построить таблицы сложения и умножения наименьших неотрицательных вычетов по mod 7.

1.2. Пусть m > 0, (a, m) = 1, b – целое и x пробегает полную, а приведенную систему вычетов по модулю m. Доказать, что 1.3. Найти наименьшее положительное число, при делении которого на 17, 13 и 10 получаются остатки соответственно 15, 11 и 3.

1.4. Доказать, что показатель, с которым данное простое число p входит в произведение n!, равен [n/p] + [n/p2 ] + [n/p3 ] +....

1.5. Найти все первообразные корни по модулям 9, 11, 14, 17, 18.

1.6. Не прибегая к алгоритму Эвклида, доказать, что если (a, b) = d, то найдутся два таких целых s и t, которые удовлетворяют условию as + bt = d.

1.7. Доказать теорему Вильсона: (p 1)! 1(mod p), где p простое.

1.8. Пусть целое a > 1. Доказать, что простые нечетные делители числа ap 1 делят a 1 или имеют вид 2px + 1, где p – простое нечетное число.

1.9. Пусть целое a > 1. Доказать, что простые нечетные делители числа ap + 1 делят a + 1 или имеют вид 2px + 1, где p – простое нечетное число.

1.10. Придумать доказательство теоремы Ферма, отличное от доказательства в тексте.

1.11. Вывести теорему Эйлера из теоремы Ферма.

1.12. Полагая N = 3 · 5, 3 · 7, 5 · 7, 3 · 11, провести процедуру шифрования-дешифрования для разнообразных значений M.

Глава 2.

Элементы теории групп, колец и полей 2.1. Множество с операцией Пусть дано некоторое множество M элементов. Говорят, что в M определена алгебраическая операция, если всяким двум (различным или одинаковым) элементам множества M, взятым в определенном порядке, по некоторому закону ставится в соответствие вполне определенный элемент, принадлежащий этому же множеству M.

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

Изображать ее мы будем либо в виде умножения ab, либо в виде сложения a + b, смотря по случаю. Примеры некоммутативной операции приведены ниже.

2.2. Обратная операция Говорят, что для операции, заданной в M, существует обратная операция, если при любых a M и b M каждое из уравнений имеет решение и при том единственное.

Решить сравнение 3x 2( mod 11). Нетрудно проверить, что решением будет x 8(mod11). Имеем 3x = 2+11x1 = 9x1 +2x1 +2, 2x1 +2 = 3x2, Легко видеть, что не для всякой операции в множестве M существует обратная операция. Например, для сложения натуральных чисел и умножения целых чисел.

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

Определение 2.3.1. Непустое множество G называется группой, если выполняются следующие условия:

1.1). Множество замкнуто относительно некоторой операции.

1.2). Операция ассоциативна:

1.3). В G выполняется обратная операция.

Группа называется абелевой, если всегда Некоммутативную группу даёт Некоммутативная операция — умножение перестановок в симметрической группе. Вообще, перестановкой степени n называется заменяющая в множестве элементов 1, 2,..., n элемент l на il.

Имеется n! перестановок из n элементов. Последовательное выполнение двух перестановок есть снова перестановка, и эта операция называется произведением перестановок.

Ниже левые части двух равенств отличаются порядком сомножителей, а потому отличаются и правые части:

50 Глава 2. Элементы теории групп, колец и полей Читателю известна по крайней мере еще одна некоммутативная операция — умножение матриц. Некоммутативность заключена в несимметричности самой фразы, выражающей принцип умножения: "строка на столбец", где одно слово — подлежащее, а другое — дополнение. Умножение матриц будет коммутативным, только если они симметричны относительно главной диагонали.

Существуют другие определения группы, например:

Определение 2.3.2. Непустое множество G называется группой, если выполняются следующие условия:

2.1) Множество G замкнуто относительно некоторой операции.

2.2) Операция ассоциативна, 2.3) Для каждого a G существует хотя бы одна (левая) единица т.е. такой элемент, который оставляет элемент a неизменным.

2.4) Для каждого a G существует хотя бы один (левый) обратный элемент Легко показать, однако, что из первого определения следует второе.

Действительно, пусть уравнение xa = b разрешимо при любых a и b.

Тогда разрешимо и уравнение Обозначим решение этого уравнения через x = e, т.е. ec = c.

Покажем, что это решение и есть (левая) единица, каково бы ни было c.

Опираясь на разрешимость уравнения ax = b, cоставим уравнение где a произвольный элемент, и умножим его слева почленно на Но выше было и потому Однако одновременно по условию и, значит, Отсюда следует, что для любого a G, (так как a произвольно).

Условие 2.4 непосредственно следует из разрешимости уравнения xa = 1.

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

Умножим это равенство сначала справа на а затем слева на Это можно сделать, так как по доказанному левый обратный элемент (a1 )1 для a1 существует.

Теперь воспользуемся ассоциативностью операции умножения:

(a1 )1 (a1 a)a1 = (a1 )1 (1a1 ) = (a1 )1 a1 = 1.

С другой стороны, Поэтому т.е.

и левый обратный элемент есть и правый обратный.

Далее, в выражении a1 заменим 1 на Получим так как по доказанному только что a1 является также и правым обратным элементом. Иначе говоря, a1 = 1a, т.е левая единица является одновременно и правой, что и требовалось.

Доказательство того, что из второго определения следует первое — тривиально. Разрешимость уравнений т.е. наличие обратной операции, следует из наличия правого и одновременно левого обратного элемента a1 :

Так вводится деление, как операция, обратная умножению.

Обратный элемент произведения равен произведению обратных элементов, взятых в обратном порядке:

(ab)1 = b1 a1, так как (b1 a1 )(ab) = b1 (a1 a)b = 1.

Можно иначе.

Найдём x в уравнении (ab)x = 1. Для этого умножим обе части слева сначала на a1 :

а затем на b1 :

Аналогично, пусть x(ab) = 1. Умножим обе части справа сначала на b1 :

а затем на a1 :

Если условиться,что то легко видеть, что Далее, полагая получим Группа по умножению называется мультипликативной группой, а группа по сложению — аддитивной. Обратному элементу a1 в мультипликативной группе отвечает противоположный элемент a в аддитивной, а единице отвечает нуль. Для абелевых групп иногда целесообразно записывать групповую операцию аддитивно, т.е. писать a + b вместо ab. Вместо a + (b) можно кратко писать a b, так как разность a b есть решение уравнения x+b = a. В самом деле, положив x = ab, и подставив это в уравнение, получим (ab)+b = a+(b+b) = a+0 = a, т.е. a b удовлетворяет уравнению. Так вводится вычитание, как операция, обратная сложению.

2.4. Порядок группы и порядок элемента группы Определение 2.4.1. Число элементов конечной группы называется порядком группы.

Если все степени элемента a группы являются различными элементами группы, то a называется элементом бесконечного порядка. Если же среди них имеются одинаковые (в случае конечной группы это обязательно имеет место), например, Это означает, что существуют степени, равные 1.

Определение 2.4.2. Порядком элемента a группы называется наименьшее целое n > 0, при котором Иными словами, если n есть порядок элемента a, то при n > 0, и то k n.

(Ср. с определением 1.11.1) В этом случае говорят, что a есть элемент порядка n.

Отсюда, умножив обе части (2.4.2) на a1, сразу имеем a1 = an1.

Теорема 2.4.3. Если элемент a имеет порядок n, то 1) Все элементы 1, a,..., an1 различны.(Ср. с утверждением 1.11.2)) 2) Всякая другая степень элемента a, положительная или отрицательная, равна одному из этих элементов.

Действительно, если что противоречит условию теоремы, так как k l < n.

Далее, если Наконец, если ak = 1, то и ar = 1. Отсюда ak = (an )q, и k кратно n.

Определение 2.4.4. Наибольший из порядков элементов группы называется показателем группы.

В случае бесконечной группы говорят о группе бесконечной мощности, употребляя иногда словосочетание "группа бесконечного порядка".

2.5. Примеры групп 1. Аддитивная группа целых чисел Z.

2. Аддитивная группа всех рациональных чисел Q.

3. Аддитивная группа действительных чисел R.

4. Аддитивная группа комплексных чисел C.

5. Аддитивная группа всех четных чисел.

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

6. Все отличные от нуля рациональные числа уже образуют группу по умножению: мультипликативную группу рациональных чисел.

7. Мультипликативная группа положительных рациональных чисел Q.

8. Мультипликативная группа положительных действительных чисел R.

9. Аддитивная группа классов вычетов по модулю m.

10. Мультипликативная группа классов вычетов приведенной системы по модулю m.

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

12. Невырожденные квадратные матрицы порядка n образуют некоммутативную мультипликативную группу.

13. Группа вращений правильных многогранников.

14. Симметрическая группа, т.е. группа Sn подстановок (некоммутативная) порядка |Sn | = n! и степени n.

15. Группа всех pn векторов длины n с основанием p и операцией поразрядного сложения по модулю p.

2.6. Подгруппы Определение 2.6.1. Подмножество H группы G называется подгруппой этой группы, если оно само является группой 56 Глава 2. Элементы теории групп, колец и полей относительно операции, определенной в группе G.

Для установления факта, является ли (непустое) подмножество H элементов группы G подгруппой группы G, достаточно проверить 1) Замкнутость множества относительно данной операции.

2) Содержится ли в H вместе с a также и a1.

Ассоциативность следует автоматически, так как она имеет место в G.

Наличие единицы следует из 1) и 2).

В случае конечной группы условие 2) автоматически следует из 1): вместе с a вследствие замкнутости в H содержится и произведение aa... a. Так как группа конечна, то найдется такое n, что an = 1, и Для абелевой группы, где групповая операция записывается аддитивно, достаточно потребовать, чтобы вместе с a и b содержалась и разность a b. (Вместо требования, чтобы содержались a + b и a.) 1. Единичная группа, т.е. группа, состоящая только из единицы, и вся группа — несобственные подгруппы. Остальные — собственные, или истинные.

2. Подгруппой аддитивной группы целых чисел является множество всех целых чисел, кратных некоторому m.

3. Подгруппа группы всех pn векторов с основанием p.

4. Подгруппа всех четных подстановок симметрической группы, так называемая, знакопеременная группа.

5. Подгруппа симметрической группы, оставляющая на месте фиксированный элемент.

2.7. Порождающие элементы и циклические группы Утверждение 2.7.1. Пересечение G0 = G1 G2... Gn групп G1, G2,..., Gn также будет группой.

Действительно, во-первых, G0 не пусто, так как всем подгруппам G1, G2,..., Gn принадлежит единица группы. Если единица — единственный элемент в G0, то G0 несобственная подгруппа. Пусть, далее, G0 содержит элементы, отличные от единицы, т.е. a, b G0. Тогда a, b Gi, i = 1, 2,... n, а значит, ab Gi, и потому ab G0. Таким образом, G0 замкнуто. Далее, если a G0, то a Gi, i = 1, 2,... n, а значит, a1 Gi, и потому a1 G0 Таким образом, G0 вместе с a содержит a1. Если a является единственным отличным от единицы элементом в G0, то это означает, что он обратный самому себе, т.е. a = a1.

следовательно, a есть элемент второго порядка: a2 = 1. Этим завершается доказательство.

Пусть теперь a, b,..., c — любые элементы группы G. Возьмем пересечение всех подгрупп группы G, которые содержат все эти элементы. Это пересечение есть подгруппа. Она называется подгруппой, порожденной элементами a, b,..., c, и состоит из всех произведений и степеней (в том числе и отрицательных) элементов a, b,..., c. Если взять только один единственный элемент a = 1 (a = 0, на случай аддитивной группы), то он порождает группу всех степеней a±i, включая a0 = 1 ( всех кратных ±ia, включая 0a = 0 на случай аддитивной группы).

Определение 2.7.2. Группа, порожденная одним элементом, называется циклической.

Оговорка a = 1 (a = 0, на случай аддитивной группы), которая обычно подразумевается, необходима, так как в противном случае единственным элементом может оказаться только a = (a = 0,), и группа будет состоять только из одного элемента.

Циклическую группу, порожденную элементом b, обычно обозначают символом {b}.

Всякая циклическая группа — коммутативна (абелева).

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

2.8. Подгруппы циклической группы Пусть G — циклическая группа, и H — ее истинная подгруппа.

Пусть G — есть совокупность степеней элемента a. Тогда и подгруппа H есть совокупность степеней элемента a.

Пусть al — наименьшая из положительных степеней. В таком случае в H содержатся и все степени (al )q. Покажем, что ничего другого подгруппа H не содержит. В самом деле, пусть имеется такой элемент ak, что k = ql + r, (0 < r < l). Имеем, ak = aql+r = aql ar, aql H; aql H, aql aql ar H, ar H, и получается, что не l, а r есть наименьший из показателей в подгруппе H, чего быть не может.

Отсюда следует Теорема 2.8.1. Подгруппа циклической группы сама циклическая. Она состоит либо из единицы группы, либо из всех степеней элемента al, имеющего наименьший возможный положительный показатель l, (где a — элемент, порождающий всю исходную группу G.) Пусть a — элемент конечного порядка n, то есть an = 1, Тогда порядок группы есть n, и n должно делиться на l. Действительно, так как 1 принадлежит подгруппе H, и так как 1 = an, то an также принадлежит подгруппе H. А так как все элементы подгруппы H суть степени элемента al, то n кратно Если же a — элемент бесконечного порядка, то и группа H имеет бесконечный порядок и состоит из элементов Следовательно, в случае группы бесконечного порядка число l произвольно, а в случае группы конечного порядка n каждому его делителю l соответствует циклическая подгруппа {al } порядка q = n/l циклической группы G.

Элемент a называется порождающим или первообразным элементом группы G.

Вспомним пример с первообразными корнями по модулям m = 2, 4, p, 2p, т.е., например, по модулям m = 9, 11, 18.

Следовательно, приведённые системы вычетов по этим модулям оказываются циклическими группами, а делители числа (m) суть порядки их подгрупп..

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

Пусть опять a первообразный элемент, и b = am, где m не только не делит n, но и (m, n) = 1.

Если бы элемент b = am принадлежал какой-нибудь истинной подгруппе H группы G, то m было бы кратно какомунибудь делителю l числа n, что невозможно из-за (m, n) = 1.

Отсюда следует, что все степени различны, так как в противном случае элемент b = am порождает истинную подгруппу H, которой и принадлежит, вопреки доказанному выше.

Иначе говоря, вместе с элементом a порождающими элементами группы будут все такие степени am, что (m, n) = 1.

Этот же факт устанавливается следующим простым рассуждением. Все степени bj = ajm таковы, что благодаря условию (m, n) = 1, показатели jm пробегают вместе с j полную систему вычетов по модулю n (см. теорему 1.6.2). Если же (m, n) = d > 1, то m = m1 d и (m1, n) = 1. Тогда, положив b = am1, получим что b — первообразный элемент, и bd = am1 d = am — суть d-я степень порождающего элемента a.

А она по доказанному выше порождает циклическую подгруппу порядка n/m1 = d.

Таким образом, первообразных элементов циклической группы порядка n имеется ровно столько, сколько чисел, взаимнопростых с n, имеется среди чисел 1, 2,..., n 1, т.е. (n).

Покажем теперь, что для каждого делителя l порядка n циклической группы G существует только одна подгруппа H порядка n/l, хотя, быть может, делитель l входит в число n как степень lx.

Действительно, предположим противное, и пусть имеется еще одна подгруппа H, состоящая из lх степеней элемента m, где (m, n) = 1, и потому b вместе с a является также b=a порождающим элементом группы G. Иначе говоря, пусть Подчеркнем, что последнее чисто "теоретико-числовое" рассуждение не было бы возможным, не будь здесь главы 1, которой нет в большинстве руководств по теории групп.

две циклические подгруппы порядка = n/l. Переписав заметим, что из-за (m, n) = 1, последовательность m, 2m,... m, по теореме 1.6.2 пробегает полную систему вычетов по модулю. Пусть im j(mod), где j — это одно из чисел 1, 2,...,, составляющих полную систему наименьших положительных вычетов по модулю. Имеем im = j + t.

Отсюда aiml = a(j+t)l = ajl atl = ajl atn = ajl (an )t = ajl, а это означает, что подгруппы H и H отличаются только порядком следования их элементов, а потому совпадают.

Пусть группа G есть циклическая группа порядка n = 63, и пусть — её порождающий (первообразный, образующий) элемент. Числа 3, 7, 9, 21 — суть делители порядка группы G.

Подгруппа H3 G порождается элементом 3. Имеем В свою очередь В четырёх подгруппах содержится 27 различных элементов. Так как (63) = 36, то остальные 36 элементов являются порождающими (первообразными, образующими) элементами группы G, и потому никакой истинной подгруппе принадлежать не могут.

На случай приведенных систем вычетов это означает, что первообразных элементов (корней) циклической группы приведенной системы вычетов по модулю m имеется где m = 2, 4, p, 2p.

2.9. Смежные классы.

Разложение группы по подгруппе Пусть H = {h1, h2,..., hi,...} подгруппа группы G, и a G.

Определение 2.9.1. Множество aH = {ah1, ah2,..., ahi,...} называется левосторонним (левым) смежным классом группы G, по подгруппе H. Множество Ha называется правосторонним, (правым) смежным классом группы G, по подгруппе Рассмотрим последовательность смежных классов:

где Утверждение 2.9.2. Всякий смежный класс определяется любым своим элементом.

Действительно, пусть Возьмём произвольный элемент ahj aH. Тогда Так как hj hi H, и так как по определению группы разрешимо уравнение hj x = hk, т.е. для любого hk H найдётся такое hi H, что hk = h1 hi, то правые части в (2.9.3) и (2.9.4) совпадают с точностью до порядка следования (перестановки) элементов. Отсюда следует Утверждение 2.9.3. Смежные классы либо не пересекаются, либо совпадают. Это значит, что при заданной подгруппе H G каждый элемент a G принадлежит в точности одному смежному классу.

Вся группа G распадается на непересекающиеся смежные классы по подгруппе H.

Утверждение 2.9.4. Все смежные классы равномощны, так как соответствием ahi bhi, имеющим место для каждого i, устанавливается взаимно однозначное отображение aH в bH.

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

Утверждение 2.9.5. Два элемента a и b принадлежат одному и тому же смежному классу тогда и только тогда, когда a1 b H.

Д о к а з а т е л ь с т в о. Пусть a1 b H, тогда это значит, что т.е. b принадлежит смежному классу aH, определяемому элементом a.

Обратно, пусть hi H. Положим b = ahi, т.е. b принадлежит смежному классу aH, определяемому элементом a. (Это и означает, что a и b принадлежат одному и тому же смежному классу.) Тогда т.е. a1 b H.

Утверждение 2.9.6. За исключением самой подгруппы H смежные классы по ней не являются группами.

Действительно, если a G, но a H, то и a1 H. Поэтому и 1 aH.

Утверждение 2.9.7. Для произвольной подгруппы H элементы, обратные к элементам левого смежного класса, образуют правый смежный класс.

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

Определение 2.9.8. Число различных смежных классов в разложении группы G по подгруппе H называется индексом подгруппы H в группе G. Он может быть конечным и бесконечным. Если число смежных классов конечно, то H называется подгруппой конечного индекса.

Обозначив порядок (конечной!) группы G символом n, порядок и индекс подгруппы H соответственно j и i, получим, что справедлива Теорема 2.9.9 (Лагранж).

Отсюда следует Утверждение 2.9.10. — порядок подгруппы конечной группы есть делитель порядка группы.

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

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

Заметим попутно, что если циклическая группа G порождается элементом a, и её подгруппа H порождается элементом al, то число l в формулировке теоремы 2.8.1 есть индекс подгруппы H в группе G.

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

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

Д о к а з а т е л ь с т в о. Пусть показатель группы, и a = 1.

Пусть порядок элемента b, т.е. b = 1. Тогда порядок l элемента ab есть l = m(, ). Но ab есть элемент группы, и его порядок l не может быть больше показателя группы по определению последнего. Отсюда порядок l. Значит, порядок l =. Поэтому и m(, ) =, и делит, что и требовалось.

2.10. Нормальные делители Определение 2.10.1. Подгруппа H называется нормальным делителем или инвариантной подгруппой, когда все левые смежные классы являются одновременно и правыми смежными классами, т.е., когда для всех a.

Важно подчеркнуть, что (2.10.5) вовсе не означает, что для всякого h H ah = ha. Если для коммутативной группы это действительно так, то в некоммутативном случае это означает лишь, что для каждого h1 H найдется такое h2 H, что ah1 = h2 a. Если групповая операция не коммутативна, то соотношение (2.10.5) означает "перестановочность".

В абелевой группе любая подгруппа — нормальный делитель.

Утверждение 2.10.2. Если H нормальный делитель, то произведение смежных классов есть снова смежный класс.

Действительно, так как операция ассоциативна, то что и требовалось.

Утверждение 2.10.3. Если произведение любых двух смежных классов в разложении группы G по подгруппе H есть снова смежный класс, то подгруппа H есть нормальный делитель.

Тогда после умножения этого равенства на a1 слева получим.

HbH = a1 cH, и H(bH) есть левый смежный класс, который содержит смежный класс bH, а значит, совпадает с ним, т.е.

HbH = bH. Но (Hb)H содержит также и правый смежный класс Hb, и потому совпадает с ним.

Значит, bH = Hb, и H есть нормальный делитель.

Утверждение 2.10.4. Если H есть нормальный делитель, то каждому смежному классу в разложении группы G по подгруппе H есть "обратный", т.е. такой xH (или Hx), что aHxH = xHaH = H.

Действительно, если ax = 1, т.е. x = a1, то Или, что то же, если xa = 1, т.е. x = a1, то Объединяя утверждения 2.10.2, 2.10.3 и 2.10.4, получим:

Утверждение 2.10.5. Множество смежных классов по нормальному делителю H есть группа. Ее порядок равен индексу подгруппы H в группе G. Эта группа обозначается символом G/H и называется фактор-группой группы G по нормальному делителю H.

2.11. Изоморфизм групп Определение 2.11.1. Изоморфизм двух групп G и G есть такое взаимно однозначное соответствие a a, a G, a G, при котором из того, что b b, c c, и bc = d, bc = d, следует d d.

Примеры изоморфизма групп:

1. Циклическая мультипликативная группа 1, a±1, a±2,...

изоморфна аддитивной группе всех целых чисел.

2. Все циклические группы 1, a, a2,..., an одного порядка изоморфны друг другу.

3. Аддитивная группа всех действительных чисел изоморфна мультипликативной группе всех (отличных от нуля) положительных вещественных чисел. Изоморфизм устанавливается соответствием log a a. Имеем:

Пусть С одной стороны, С другой — Отсюда Обозначение изоморфизма:

Теорема 2.11.2 (Кэли). Всякая конечная группа порядка n изоморфна некоторой подгруппе симметрической группы степени n.

Действительно, пусть группа G имеет порядок n, и пусть элементы этой группы записаны в определенном порядке:

Если b есть произвольный элемент группы G, то все произведения ai b = ai (i = 1, 2,..., n.) различны между собой, т.е. система a1, a2,... an, есть перестановка (сдвиг) элементов группы G. Это ставит в соответствие элементу b группы G Значит, и каждому элементу группы G ставится в соответствие вполне определенная подстановка n-й степени.Двум различным элементам соответствуют различные подстановки, так как в противном случае из a1 b = a1 b следовало бы b = b.

Найдем подстановку, отвечающую элементу bc, c G.

Если элементу c отвечает подстановка т.е. ai c = ai, то из следует, что элементу bc отвечает подстановка Из теоремы 2.11.2 и из очевидного утверждения, что конечная группа может обладать лишь конечным числом подгрупп, следует, что существует лишь конечное число неизоморфных конечных групп данного порядка n.

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

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

2.12. Гомоморфизм групп Определение 2.12.1. Пусть в двух множествах M и M определены некоторые соотношения между элементами, и пусть каждому элементу a M поставлен в соответствие один и только один элемент a M таким образом, что 1) Каждому элементу a M отвечает по крайней мере один элемент a M, 2) Все соотношения между элементами множества M выполняются и для соответствующих элементов множества 68 Глава 2. Элементы теории групп, колец и полей Такое соответствие называется гомоморфизмом. Говорят также, что множество M гомоморфно отображается на множество M.

Элемент a есть гомоморфный образ элемента a, и элемент a есть прообраз элемента a. Гомоморфным будет соответствие между множеством M = Z целых чисел и множеством M классов вычетов по модулю m, если каждому числу поставить в соответствие класс вычетов, которому оно принадлежит.

Теорема 2.12.2. Гомоморфный образ G группы G есть группа.

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

т.е. в выполняется ассоциативность операции.

2) Замкнутость относительно операции следует из гомоморфизма.

3) Из того, что для всех a G выполняется a·1 = a, следует, что для всех a G выполняется a · 1 = a.

Иначе говоря, из существования единицы в следует существование единицы в Иначе говоря, из существования обратного элемента b = a1 в G следует существование обратного элемента b = a1 в G.

Согласно утверждениям 2.10.2, 2.10.3 и 2.10.4 множество смежных классов группы по подгруппе замкнуто относительно групповой операции, и в нем выполняется обратная операция тогда и только тогда, когда подгруппа есть нормальный делитель. Это же утверждение получается из теоремы 2.12.2 о гомоморфизме, как её частный случай:

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

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

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

Любая группа, гомоморфная данной, изоморфна некоторой её фактор-группе.

2.13. Несколько замечаний а) В абелевой группе каждая подгруппа — нормальный делитель.

б) Если групповая операция есть сложение, то группы и их подгруппы принято называть модулями.

в) Пусть G модуль и M его подмодуль. Смежные классы a+M, называются классами вычетов по модулю M, а фактор-группа G = G/M называется фактор-модулем модуля G по подмодулю г) Два элемента a, b лежат в одном смежном классе или классе вычетов, если их разность лежит в M. Такие два элемента называются сравнимыми по модулю M.

Это записывается следующим образом:

Рассмотрим модуль классов вычетов, т.е. совокупность a1 + +M, a2 +M,..., ai +M,... Пусть a и b принадлежат этому модулю и по гомоморфизму соответствуют элементам a, b. Тогда из (2.13.6) следует Наоборот, из (2.13.7) следует (2.13.6).

Из (2.13.6) и (2.13.7) получается, что при гомоморфизме сравнения переходят в равенства.

Сказанное выше – это чисто абстрактное теоретико-групповое рассуждение, безотносительно к какой бы то ни было конкретной интерпретации.

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

модуль. Множество всех чисел, кратных числа m, есть ее подмодуль. Обозначим его M. В главе 1 введена запись если m|(ab). Знакомое нам множество классов вычетов по модулю m является модулем, точнее фактор-модулем модуля Z всех целых чисел по подмодулю M. Классы вычетов по модулю m, т.е.элементы фактор-модуля, могут быть представлены числами 0, 1,..., m1, и фактор-модуль есть циклическая группа порядка m.

2.14. Кольцо Определение 2.14.1. Кольцом называется такая система элементов с определёнными в ней сложением a+b и умножением a · b, что:

1) По сложению она — абелева группа.

2) Умножение ассоциативно.

3) Сложение и умножение связаны законами дистрибутивности:

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

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

Закон дистрибутивности имеет место также и для вычитания, так как в кольце вычитание имеет место, как в группе по сложению. Действительно, выясним, чему равно a(b c)?

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

Иначе говоря, если один из сомножителей равен нулю, то произведение равно нулю.

Может случиться, что обратное неверно, т.е. из того, что произведение равно нулю, необязательно следует равенство нулю хотя бы одного сомножителя. В качестве примера рассмотрим кольцо классов вычетов по составному модулю m = ab. То, что множество классов вычетов — аддитивная группа, отмечено выше. Перемножим два числа и мы получили число, кратное модуля, т.е. число, принадлежащее нулевому классу вычетов. Таким образом, в кольце классов вычетов по составному модулю m = ab два класса вычетов {a} и {b} являются делителями нуля: {a}{b} = {m} = 0.

Определение 2.14.2. Кольцо без делителей нуля называется областью целостности.

Кольцо не обязано иметь единицы, так как от него не требуется быть мультипликативной группой. Кольцо называется кольцом с единицей, если она есть, и — кольцом без единицы, если её нет. Если кольцо с единицей, то 1 + 1 +... + 1 = n, и, таким образом, n есть элемент кольца.

2.15. Поле Определение 2.15.1. Если отличные от нуля элементы коммутативного кольца образуют группу по умножению, то это кольцо называется полем. (В некоммутативном случае — телом.) Теорема 2.15.2. Поле не имеет делителей нуля.

каждый ненулевой элемент имеет обратный. Для a это будет a1.

Умножим на него обе части равенства ab = 0. Получим a1 ab = 0, b = 0, что противоречит условию.

Теорема 2.15.3. Конечная область целостности есть поле.

ax элемент x пробегает все ненулевые элементы кольца. Покажем, что различным x отвечают различные ax. Действительно, предположим противное, т.е. пусть при имеет место Тогда a(x1 x2 ) = 0. Значит, так как a = 0, и делителей нуля нет, то x1 x2 = 0, откуда x1 = x2, что противоречит условию (2.15.8). Значит, множество ненулевых элементов кольца отображается на себя. Но в силу конечности кольца такое отображение может быть только взаимно однозначным.

Иначе говоря произведение ax пробегает в точности по одному разу все ненулевые элементы кольца. Следовательно, каждый ненулевой элемент b может быть представлен в виде b = ax, что означает разрешимость уравнения (2.2.1). Остаётся вспомнить определение 2.3.1 группы. (Ср. с доказательствами теорем 1.6. и 1.7.2).

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

Утверждение 2.15.4. Кольцо классов вычетов по модулю m будет полем тогда и только тогда, когда m простое число.

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

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

Поле классов вычетов по простому модулю p будем обозначать символом GF (p). Иначе говоря, полем GF (p) является полная система неотрицательных вычетов по модулю p, и операции сложения и умножения чисел 0, 1, 2,..., p 1 выполняются по модулю p. В связи с доказанными фактами снова уместно вспомнить теорему 1.7.2 о приведенной системе вычетов.

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

2.16. Идеал Непустое подмножество v кольца V само будет кольцом тогда и только тогда, когда 1. v — есть подгруппа аддитивной группы кольца, т.е. когда для любых 2. Для любых Среди подколец особую роль играют идеалы.

Определение 2.16.1. Идеалом называется такое подкольцо v кольца V, что Примеры идеалов. Нулевой идеал (0), состоящий из одного элемента 0. Единичный идеал (e), состоящий из всего кольца V.

Идеал (a), порождённый элементом a, и состоящий из всевозможных выражений Рассмотрим существо этой конструкции. Положим, что элемент a принадлежит идеалу. Тогда по определению идеала элемент ra, r V, также должен принадлежать идеалу. Кроме того, так как идеал есть кольцо, то элемент a, повторенный слагаемым сколько угодно раз, также должен принадлежать идеалу. Значит, вместе с элементом a идеалу должны принадлежать все элементы вида Проверим, что построенная таким образом конструкция действительно есть идеал. То, что (a) есть кольцо, проверяется непосредственно, так как разность двух элементов такого вида есть снова элемент такого вида:

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

Пусть s V. Тогда s(ra + na) = (sr + ns)a. т.е. имеет вид Вспомним, что означает na для колец без единицы и колец с единицей. Если кольцо с единицей, то n·1 V, т.е. n является элементом кольца. Тогда и идеал состоит из обыкновенных кратных. Например, идеал (5) в кольце целых чисел состоит из всех чисел кратных 5.

Идеал, порождённый одним элементом, называется главным. Идеал (0) — всегда главный. Кольцо, в котором все идеалы главные, называется кольцом главных идеалов. Совокупность всех кратных ra элемента a есть идеал. Нетрудно показать что этот идеал может не совпадать с главным идеалом (a).

Для этого в качестве примера рассмотрим кольцо четных чисел V = 2i, (i = ±1, ±2,...... ± j...). В этом кольце все числа, кратные некоторого a = 2i, составляют идеал и имеют вид 2i2j = 4ij, т.е. делятся на 4. С другой стороны, главный идеал содержит числа, которые при нечетном n не делятся на 4.

В дальнейшем будут рассматриваться главные идеалы как кратные.

Утверждение 2.16.2. Пересечение идеалов есть идеал.

Читатель легко справится с доказательством самостоятельно, используя метод доказательства утверждения 2.7.1.

Кроме нулевого и целого идеала, поле не содержит других идеалов. Действительно, если a = 0 принадлежит идеалу, то так как в поле имеется и a1, идеалу принадлежит и aa1 = 1, а значит любой элемент, кратный единицы, т.е. все элементы поля.

2.17. Линейное векторное пространство Определение 2.17.1. Линейным векторным пространством над полем F называется множество V векторов, удовлетворяющее условиям:

1) Множество V является аддитивной абелевой группой.

3) Выполняются дистрибутивные законы, т.е.

4) Умножение ассоциативно, т.е. (cd)v = c(dv).

Элементы c, d поля F называются скалярами.

Подмножество векторов пространства V называется подпространством, если в нем выполняются условия определения 2.17.1 Пусть A V есть подпространство пространства V. Векторы v1, v2,..., vk A называются линейно зависимыми над полем F, если найдутся такие не все равные нулю элементы В противном случае векторы v1, v2,..., vk A называются линейно независимыми. Максимальное число k линейно независимых векторов подпространства A называется его размерностью, а сама совокупность этих векторов называется базисом подпространства.

2.18. Задачи к главе 2.1. Существуют две неизоморфные группы четвертого порядка. Доказать.

2.2. Каждая группа порядка, не превосходящего пяти, абелева.

Доказать.

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

2.4. Если индекс подгруппы равен двум, то подгруппа есть нормальный делитель. Доказать.

2.5.Найти разложение циклической группы 10-го порядка по всем ее подгруппам.

2.6. Найти разложение бесконечной циклической группы, порожденной элементом x, по подгруппе, порожденной элементом x3.

2.7. Если G – циклическая группа с порождающим элементом a, и ее подгруппа H порождена степенью al, то элементы 1, a, a2,..., al1 – представители различных смежных классов.

2.8. Пусть порядок элемента x некоторой группы равен pq, и (p, q) = 1. Доказать, что найдутся такие элементы u и v, для которых выполняются равенства: x = uv = vu, up = 1, v q = 1.

2.9. Найти правое разложение симметрической группы S3 по подгруппе, состоящей из двух элементов, e и транспозиции ( 2).

2.10. Пусть H1 и H2 две подгруппы конечной группы G порядков соответственно m1 и m2. Доказать, что множество H1 H состоит из m1 m2 /d элементов, где d есть порядок пересечения подгрупп H1 и H2.

2.11. Что представляют собой разложения группы G по ее несобственным подгруппам.

2.12. Каждая циклическая группа порядка m изоморфна аддитивной группе классов вычетов по модулю m.

2.13. Найти все разложения группы 10-го порядка по всем ее подгруппам.

2.14. Сколько существует различных множеств представителей правого разложения группы 12-го порядка по ее подгруппе порядка 3?

2.15. Пусть H — произвольная подгруппа группы G, и N некоторый нормальный делитель группы G. Доказать, что HN является подгруппой группы G, причем HN = N H.

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

2.17. Построить поле, состоящее из трех элементов 0, +1, 1.

2.18. Совокупность всех кратных ra элемента a есть идеал. Показать (на примере кольца четных чисел), что этот идеал может не совпадать с главным идеалом (a).

2.19. Доказать теорему Вильсона: (p 1)! 1(modp).

Глава 3.

Конечные поля 3.1. Конечное поле как множество классов вычетов по модулю неприводимого многочлена Оказалось плодотворным разбиение кольца целых чисел на классы вычетов по простому модулю p. Множество этих классов (см. теорему 1.7.2) образует поле.

Теперь рассмотрим множество F [x] всех многочленов f (x) всевозможных неотрицательных степеней с коэффициентами из поля GF (p). В таком случае говорят о многочленах "над полем GF (p)". Введем в рассмотрение неприводимый над полем GF (p) многочлен p(x) степени m.

Определение 3.1.1. Многочлен p(x) = a0 + a1 x +... + am xm называется неприводимым над полем GF (p), если он не распадается на множители над этим полем.

В множестве F [x] неприводимый над полем GF (p) многочлен p(x) некоторой степени m играет роль, аналогичную той, которую играет некоторое простое число p в кольце целых чисел.

Рассмотрим все остатки от деления многочленов из F [x] на p(x). Они имеют вид b(x) = b0 +b1 x+...+bm1 xm1, bi GF (p).

Нетрудно посчитать, что всего таких остатков имеется в точности pm.

Два многочлена из множества F [x] называются сравнимыми по модулю многочлена p(x), если при делении на p(x) они дают одинаковый остаток. Таким образом, множество F [x] распадается на непересекающиеся классы многочленов, сравнимых по модулю p(x). Обозначим множество этих классов символом Очевидно, множество (3.1.1) замкнуто относительно сложения и вычитания над GF (p), а выполняя умножение элементов из (3.1.1) по модулю неприводимого многочлена p(x), легко убедиться, что оно замкнуто также относительно умножения. Следовательно, множество (3.1.1) есть кольцо.

Теорема 3.1.2. Все остатки, которые получаются при делении на неприводимый многочлен p(x), попарно несравнимы.

Д о к а з а т е л ь с т в о. Допустим противное, т.е. пусть для некоторых двух остатков b1 (x) = b2 (x) выполняется соотношение b1 (x) b2 (x)(modp(x)).

Отсюда b1 (x) b2 (x) 0(modp(x)). Так как степень разности в левой части этого сравнения не выше, чем m 1, оно возможно только тогда, когда b1 (x) b2 (x) = 0, что противоречит условию b1 (x) = b2 (x).

Теорема 3.1.3. Кольцо (3.1.1) не имеет делителей нуля.

Д о к а з а т е л ь с т в о. Предположим противное, и пусть (b1 (x) + p(x)d1 (x))(b2 (x) + p(x)d2 (x)) 0(modp(x)).

(Здесь в каждой из скобок в левой части стоит произвольный вычет класса, определяемого вычетом b1 (x) в первой скобке и вычетом b2 (x) – во второй).

Тогда b1 (x)b2 (x) = p(x)D(x), а значит, b1 (x)b2 (x) 0(mod p(x)), чего быть не может, так как благодаря неприводимости многочлена p(x), он взаимно прост над GF (p) с каждым из многочленов b1 (x) и b2 (x). Таким образом, кольцо (3.1.1) есть область целостности, а будучи конечным, оно есть поле.

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

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

Фиксируем произвольный многочлен a(x) F [x] Теорема 3.1.4. Если многочлен b(x) пробегает множество (3.1.2), то произведение a(x)b(x) также пробегает множество (3.1.2).

Д о к а з а т е л ь с т в о. Очевидно, что произведений a(x)b(x) = 0 столько же, сколько многочленов b(x) = 0, т.е.

pm 1. Покажем, что если b1 (x) и b2 (x) несравнимы по модулю многочлена p(x), то a(x)b1 (x) и a(x)b2 (x) также несравнимы по модулю p(x). Предположим противное, т.е. пусть верно сравнение a(x)b1 (x) a(x)b2 (x)(modp(x)). Отсюда следует a(x)(b1 (x) b2 (x)) 0(modp(x)).

Так как (a(x), p(x)) = 1, то (b1 (x) b2 (x)) 0(modp(x)), и b1 (x) b2 (x)(modp(x)), что противоречит условию несравнимости b1 (x) и b2 (x).

Из теоремы 3.1.4 следует, что каков бы ни был многочлен /(p(x)) найдется такой многочлен b(x) F [x]/(p(x)), что a(x)b(x) 1(modp(x)).

Это означает, что для каждого a(x) F [x] /(p(x)) найдется обратный ему многочлен b(x) F [x]/(p(x)), и множество (3.1.2)действительно есть мультипликативная группа, каковой она и названа выше.

Рассмотрим неприводимый над GF (2) многочлен p(x) = x2 + x + 1.

F [x]/x2 +x+1 = {0, 1, x, x + 1}. F [x] 2 +x+1 = {1, x, x + 1}.

Рассмотрим неприводимые над GF (2) многочлены В обоих случаях, разумеется:

Но в первом случае а во втором Таким образом, роль различных неприводимых многочленов, по модулям которых строится поле, состоит именно в том, что они по-разному "организуют" соотношения между элементами в мультипликативной группе: они по-разному создают пары взаимнообратных элементов. Само же "содержимое" поля зависит только от степени многочлена-модуля, так как она определяет максимальную степень остатка от деления. Легко проверить, что кроме рассмотренных неприводимых многочленов, других неприводимых многочленов над GF(2) второй и третьей степени нет.

3.2. Поле разложения многочлена xp x Изложенная выше процедура называется расширением поля GF (p). Если неприводимый многочлен p(x) имеет степень m, то вместо F [x]/(p(x)) пишут GF (pm ), а вместо F [x] GF (pm ). Поле GF (pm ) называется расширением степени m поля GF (p). Группа GF (pm ) называется мультипликативной группой поля GF (pm ), и ее порядок равен pm 1. Так как порядок элемента i группы есть делитель порядка группы, то i 1 = 1. Это означает, что любой элемент группы GF (pm ) является корнем уравнения xp 1 1 = 0, а все элементы поля m ), включая = 0, являются корнями уравнения Это означает, что Говорят, что GF (pm ) есть поле разложения двучлена в левой части уравнения (3.2.3).

Подчеркнем, что, каков бы ни был неприводимый многочлен p(x), по модулю которого построено поле GF (pm ), все элементы поля являются корнями одного и того же уравнения Исключив из рассмотрения 0 = 0, получим двучлен корнями которого являются корни из единицы.

3.3. Цикличность мультипликативной группа поля Определение 3.3.1. Характеристикой поля называется такое наименьшее целое число n, что Если это число есть нуль, то поле называют полем характеристики нуль. В противном случае имеют дело с полем конечной характеристики. Нетрудно показать, что если характеристика не равна нулю, то она есть простое число p, так как в поле нет делителей нуля.

Покажем, что уравнение (3.2.3) не имеет кратных корней.

Действительно, производная от его левой части равна так как pm 0( mod p). Она не обращается в нуль, и потому не имеет общих корней с многочленом в (3.2.3).

Для дальнейшего рассмотрим Пусть поле GF (23 ) построено по модулю многочлена p(x) = 3 + x + 1. Возведем элемент x GF (23 ) в последовательные Дабы избежать недоразумения, следует принять во внимание, что (3.3.5) относится только к элементам поля и не относится к показателям степеней при них.

3.3. Цикличность мультипликативной группа поля степени, помня, что каждую степень xi следует разделить на p(x) и взять остаток от деления:

На случай, когда модуль есть p(x) = x3 + x2 + 1, получим:

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

В общем случае справедлива Теорема 3.3.2. Группа GF (pm ) циклична.

Рассмотрим уравнение xn/pi = 1, i = 1, 2,..., k. Оно имеет не более, чем n/pi решений.

Значит, имеется не более, чем n/pi < n таких элементов b, что Это значит, что в группе GF (pm ) порядка n = pm 1 для каждого i существует элемент bi с условием Рассмотрим элемент ci = bi и покажем, что он имеет порядок pi.

Действительно, С другой стороны, Это означает, что порядок элемента ci, будучи в силу (3.3.9) делителем числа pi, в то же время не равен ни одному из собi ственных его делителей (ибо все собственные делители числа pi суть степени числа pi ).

Из этого следует, что порядок элемента ci есть pi.i Это же справедливо для каждого i = 1, 2,..., k. Отсюда следует, что произведение имеет порядок, равный наименьшему общему кратному порядков сомножителей, т.е.

p1 p2...pk = n, так как они взаимно просты.

Таким образом, элемент (3.3.10) имеет порядок, равный порядку группы, а потому является образующим (первообразным) элементом, и группа GF (pm ) циклическая. Этим завершается доказательство.

3.4. Задание поля посредством корня неприводимого многочлена Дадим другой способ задания поля Галуа. Обозначим через тот класс вычетов в кольце F [x]/(p(x)), который содержит x. Тогда, так как p(x) — это многочлен, по модулю которого построено поле GF (pm ), то p() = 0. Таким образом, оказывается корнем уравнения p(x) = 0 в поле GF (pm ). Благодаря этому GF (pm ) состоит из многочленов от степени, не превосходящей m над GF (p). Говорится, что поле GF (pm ) образовано из поля GF (p) присоединением к нему корня многочлена p(x).