§ 9.4. Арифметические группы

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

Пусть натуральное число. Напомним что символом мы обозначаем множество обратимых элементов в т.е.

Покажем, что это множество образует группу относительно операции умножения классов в

Мы знаем, что произведение двух элементов из тоже принадлежит Так ли это для элементов Точнее говоря, верно ли, что произведение любых двух элементов из остается в множестве Бели нет, то умножение классов не является операцией на множестве в смысле определения из § 9.1.

Другими словами, нам нужно проверить, что произведение двух обратимых классов из тоже обратимо. Мы уже сделали это в § 5.7, но рассуждение настолько просто, а результат так важен, что мы повторим его здесь. Обозначим, как обычно, обратные элементы к через а и V соответственно. Тогда обратим, причем обратный к нему элемент равен Для проверки достаточно вычислить произведение:

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

умножение элементов ассоциативно. Единичным элементом служит 1: это обратимый элемент в и поэтому принадлежит он Тот факт, что любой элемент имеет обратный, непосредственно следует из определения Итак, множество с операцией умножения — на самом деле группа.

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

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

состоит из элемента, т. е.

Также легко вычисляется с простым Все что мы должны для этого сделать — подсчитать количество натуральных чисел, меньших чей наибольший общий делитель с равен 1. Но ввиду простоты числа равенство равносильно тому, что не делит а. Следовательно, достаточно подсчитать количество натуральных чисел, меньших не делящихся на Однако проще найти числа, делящиеся на Действительно, если делится на то

Таким образом, среди натуральных чисел, меньших имеется ровно делящихся на Значит,

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

Для общей формулы нам потребуется следующий результат.

Теорема. Если тип — взаимно простые натуральные числа, то

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

Доказательство теоремы использует геометрическую интерпретацию китайской теоремы об остатках, т.е. таблицу из § 8.3 (стр. 200). Напомним, как она строится. Мы начинаем с двух натуральных чисел, удовлетворяющих условию Далее чертим таблицу с столбцами и строками. Каждый столбец помечаем неотрицательным целым числом (слева направо, в порядке возрастания чисел) и интерпретируем эти числа как классы из Аналогично «нумеруем» строки таблицы элементами Итак, получилась таблица с клетками. В каждую из них, стоящую на пересечении столбца а и строки мы ставим натуральное число х, удовлетворяющее системе сравнений:

и неравенству: Целые числа мы называем координатами вычета х. Поскольку тип взаимно просты,

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

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

Утверждение. Класс х принадлежит группе тогда и только тогда, когда

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

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

Докажем, что обратный класс для х. Поскольку имеем:

Значит, делится на Дословно те же рассуждения показывают, что делится на Но что в силу леммы из § 3.6 обеспечивает нам делимость на произведение Другими словами,

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

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

Теперь мы готовы найти для любого натурального Прежде всего разложим в произведение простых множителей:

где По теореме

Учитывая формулу для в случае степени простого числа, выведенную выше, мы получаем

Например, для

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