Решение сравнений и их приложения

Определение 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 — приведенная система абсолютно наименьших вычетов.