Полная и приведенная системы вычетов

Определение 3. Полной системой вычетов по mod m называется система чисел взятых по одному из класса по этому модулю.

Например: по mod 6: 12,-13,2,63,-2,5

Поскольку в ПСВ число вычетов должно равняться числу классов,то класс содержит бесконечное множество вычетов, то можно составить бесчисленное множество различных полных систем вычетов по данному mod m.

a) полная система наименьших неотрицательных вычетов 0,1, ….,m-1 (в прим.0,1,2,3,4,5)

б) полная система абсолютно наименьших вычетов (составляется из наименьших по абсолютной величине) -2,-1,0,1,2,3

СВОЙСТВА

Теорема 1. Любая совокупность m чисел, попарно несравнимых по mod m есть полная система вычетов по mod m

Теорема 2. Если (a,m)= 1 и х пробегает полную систему вычетов по mod m то числа вида ах+b тоже пробегают полную систему вычетов по mod m (a,b Z)

Все числа одного и того же класса вычетов по mod m имеют с модулем m один и тот же НОД, равный (a,m).

В частности, если одно из чисел класса по mod m взаимно просто с m то и все числа класса взаимно просты с mod m.

Определение 4. Класс вычетов по mod m состоящий из чисел, взаимно простых с mod,называется примитивным классом.

Для го модуля примитивные классы существуют; такими будут, в часности классы ,

Пример m=6; ,

m=7: , , , , ,

Число примитивных классов по mod m обозначается (m) и называется функцией Эйлера. Так, обратная функция Эйлера определяет число положительных (целых), не превосходящих m и взаимо простых с m (для m>1) (6)=2; (7)=6

Если mod—простое число р, то все классы, кроме нулевого, примитивны, так что (p)=p-1

Выберим из примитивного класса по mod m по одному числу, получим привиденную систему вычетов по mod m.

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

Если в качестве исходной взять полную систему наименьших неотрицательных или абсолютно наименьших вычетов, то указанным способом получим соответственно приведенной систему наименьших неотрицательных или абсолютно наименьших вычетов по mod m.

Теорема 3. совокупность φ(m) чисел (m>1), взаимно простых с mod m, и попарно несравнимых по mod m есть приведенная система вычетов по mod m: а (1)

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