8.6. Приведенная система вычетов

• Определение. Пусть целое положительное число. Множество классов из полной системы вычетов взаимно простых с называется приведенной системой вычетов, которую будем обозначать как или Приведенную систему вычетов, следовательно, можно составить из чисел взаимно простых с модулем. Обыкновенно выделяют из системы наименьших неотрицательных вычетов: .

• Утверждение 8.6.1. является группой с операцией умножения.

Доказательство. Проверим все свойства (аксиомы) группы.

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

2. Ассоциативность операции умножения чисел выполняется.

3. Единичный элемент — 1.

4. Существование обратного элемента.

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

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

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