Определение 1. Наибольший общий делитель модуля т и любого числа а из данного класса вычетов по т называется наибольшим общим делителем т и этого класса вычетов.
Определение 2. Класс вычетов а по модулю т называется взаимно простым с модулем m, если наибольший общий делитель а и т равен 1 (то есть если т и любое число из а взаимно просты).
Пример. Пусть т = 6. Класс вычетов 2 состоит из чисел {..., -10,-4, 2, 8, 14, ...}. Наибольший общий делитель любого из этих чисел и модуля 6 равен 2. Значит, (2, 6) = 2. Наибольший общий делитель любого числа из класса 5 и модуля 6 равен 1. Значит, класс 5 взаимно прост с модулем 6.
Выберем из каждого класса вычетов, взаимно простого с модулем m, по одному числу. Получим систему вычетов, составляющую часть полной системы вычетов. Ее называют приведенной системой вычетов по модулю m.
Определение 3. Совокупность вычетов по модулю m, взятых по одному из каждого взаимно простого с т класса вычетов по этому модулю, называется приведенной системой вычетов.
Из определения 3 следует способ получения приведенной системы вычетов по модулю т: надо выписать какую-либо полную систему вычетов и удалить из нее все вычеты, не взаимно простые с m. Оставшаяся совокупность вычетов — приведенная система вычетов. Приведенных систем вычетов по модулю m, очевидно, можно составить бесчисленное множество.
Если в качестве исходной взять полную систему наименьших неотрицательных или абсолютно наименьших вычетов, то указанным способом получим соответственно приведенную систему наименьших неотрицательных или абсолютно наименьших вычетов по модулю m.
Пример. Если т = 8, то 1, 3, 5, 7 — приведенная система наименьших неотрицательных вычетов, 1, 3, -3,-1 — приведенная система абсолютно наименьших вычетов.
Теорема 2. Пусть число классов, взаимно простых с m, равно k.Тогда любая совокупность k целых чисел
(1) попарно несравнимых по модулю m и взаимно простых с m, представляет собой приведенную систему вычетов по модулю m.
