Некоторые результаты из теории групп.

Рассмотрим теперь некоторые интересные результаты теории групп, которые нам понадобятся при изложении греко-китайской теоремы об остатках. Как уже отмечалось в теореме 2.3.11, кольцо не всегда является полем, потому что в нем могут быть необратимые элементы. Мы уже рассматривали кольцо в котором элементы 2, 4 и 6 не имеют мультипликативных обратных, тогда как элементы 1, 3, 5 и 7 имеют обратные элементы. Различие проистекает из того, что 1, 3, 5 и 7 взаимно просты с 8, а для 2, 4 и 6 это не так.

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

Рис. 2.3.1. Таблица умножения группы

Пусть G — абелева группа из элементов, т.е. любые два элемента из G коммутируют между собой. Для произвольного а из G обозначим (к раз) через а; — единичный элемент группы G. Обычные соотношения для степеней по-прежнему выполняются. Справедливо следующее обобщение теоремы Ферма.

Теорема 2.3.17. Если G — абелева группа, состоящая из элементов, то для всякого а из G выполняется равенство .

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

Эта абстрактная версия теоремы Ферма справедлива и для неабелевых групп; ее доказательство можно найти где угодно (см. например, (Cnilds, 1979)).

Пусть G — группа из элементов, . Так как то S непусто и по принципу полной упорядоченности S имеет наименьший элемент ко, который называется порядком элемента а. Группа называется циклической, если в ней существует элемент а, степени которого пробегают все элементы группы. Этот элемент называется образующим или, в случае группы примитивным корнем по модулю .

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

Теорема 2.3.18. Пусть G — группа, состоящая из элементов, и пусть — порядок элемента а из G. Тогда

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

потому что G состоит из элементов. Ясно, что порядок группы G равен , где последний полученный элемент.

Теорема 2.3.19. Если — порядок элемента а из G и то к.

Доказательство. Пусть , где Если то доказывать нечего, поэтому предположим, что Тогда откуда следует, что . Это, однако, противоречит тому, что — наименьшее число со свойством

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

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

Период этих последовательностей равен 2, поэтому порядок любого отличного от единицы элемента также равен 2, порядок делит (теорема 2.3.18). Поэтому группа не циклическая, и не существует примитивных корней по модулю 8. Следующая теорема объясняет, почему это так.

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

Доказательство. Доказательство можно найти в

Оказывается, что 8 — наименьшее число, не имеющее примитивных корней. С другой стороны, по теореме 2.3.2 — циклическая группа, потому что Группа состоит из

элементов, а именно и элемент 5 является примитивным корнем, поскольку

Предлагаем читателю найти все примитивные корни по модулю 18. Непосредственно из теоремы 2.3.20 получаем

Следствие 2.3.21. Если — нечетное простое число, то группа циклическая и уравнение не имеет решений, отличных от

Как только мы нашли примитивный корень а по модулю в мы можем сразу же получить другой корень — его мультипликативный обратный по модулю . В случае в также является примитивным корнем. (Этот факт будет проверен ниже.)

Сколько примитивных корней содержится, например, в Если возвести примитивный корень в степень где , то будет другим примитивным корнем, потому что порядок элемента равен (это будет доказано ниже); в случае и, поскольку вычислим 55 в кольце Получим 11, другой примитивный корень. В общем случае число примитивных корней равно Например, в имеются два примитивных корня, 2 и 11.

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

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