8.5. Полная система вычетов
Свойства 1—3 сравнений показывают, что операция сравнения целых чисел по модулю является отношением эквивалентности. Множество всех целых чисел Z разбивается на классы эквивалентности (рис. 8.1), которые называются вычетами по модулю 
Числа 
лежат в одном классе 
т.е. 
тогда и только тогда, когда 
имеют одинаковые остатки от деления на 
Числа одного и того же класса имеют с модулем 
один и тот же наибольший общий делитель, 
из 
следует, что 
(см. п. 8.4). Особенно важны классы, для которых этот делитель равен единице, т.е. классы, содержащие числа, взаимно простые с модулем.
Рис. 8.1. Полная система вычетов
• Определение. Множество классов вычетов 
по модулю да называется полной системой вычетов 
Полную систему вычетов можно получить следующим образом. Пусть 
аддитивная (операция сложения) группа целых чисел, 
подгруппа всех чисел, кратных 
Тогда факторгруппа 
аддитивная группа вычетов по модулю 
(полная система вычетов).
