Т: Пусть число классов вычетов взаимно простых с m равно к, тогда любая совокупность к-целых чисел х1, х-2…хк попарно несравнимых по модулю m и взаимно простых с m представляет собой приведенную систему вычетов по модулю m.
Доказательство:
- 1. Очевидно, что все числа совокупности х1, х-2…хк принадлежат некоторым классам вычетов по модулю m, т.к. эти числа несравнимы по модулю m, то они принадлежат различным классам вычетов
- 2. По условию, каждое из чисел взаимно просто с m, следовательно, они принадлежат классам вычетов, которые взаимно просты с m
- 3. По условию классов вычетов, взаимно простых с m, к и чисел в совокупности к, следующая совокупность х1, х-2…хк это приведенная система вычетов по модулю m. ч.т.д.
Пр. полная система вычетов для m=12 1,2,3,4,5,6,7,8,9,10,11,12, приведенная же, это все из вышеперечисленных, которые взаимнопросты с m: 1,5,7,11.
Мультипликативная группа обратимых эл.
Zm {0,1,2…m-1}.
Т: Для того, чтобы класс вычетов, а был обратимым необходимо и достаточно, чтобы, а был взаимно прост с m.
Доказательство:
1. Пусть (а, m)=1, выберем в, а число а, тогда (а, m)=1, тогда по свойствам НОД найдутся х, у, что ах+mу=1, отсюда:
ах-1=-my, т. е. (ах-1):m>ах?1 (mod m).
х, хх, а*х=1, х Zm.
х = а-1 это значит, что класс, а обратим.
2. Пусть, а — обратим, тогда, а *х=1.
ах?1 (mod m).
ax-1 = my, y Z. ч.т.д.
Таким образом, в кольце Zm каждый класс, взаимнопростой с m, обратим.
Множество Рm замкнуто относительно умножения, ассоциативно и коммутативно, 1 Рm т.к. он обратим и каждый элемент Рm имеет себе обратный по определению. Эту группу по умножению называют мультипликативной группой элементов в кольце Zm.
