3.1.7. Классы вычетов

Числа, сравнимые по модулю т, образуют класс вычетов по модулю т. Все числа из одного класса имеют один и тот же остаток r от деления на т. Любое число а из класса вычетов называется вычетом по модулю т. Соответствующий класс обозначается через ā. Поскольку отношение ab(modт) является бинар­ным отношением эквивалентности, то имеем разбиение целых чисел на классы эквивалентности (классы вычетов). Всего имеется т классов вычетов по модулю т: .

Свойство 1. a b(mod m) <=>

Свойство 2. a  b(mod m) <=> .

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

Свойство 3. Любые т чисел, попарно несравнимые по модулю т, образуют полную систему вычетов.

Свойство 4. Если (а, т)=1 и х пробегает полную систему вычетов по модулю т, то ах + b, где b — любое целое, также пробегает полную систему вы­четов по модулю т.

Согласно свойству 11 сравнений, числа одного класса вычетов имеют с модулем т один и тот же общий делитель. Рассмотрим те классы, для которых этот делитель равен единице. Взяв от каждого такого класса по одному вычету, получим приведен­ную систему вычетов. Например, приведенная система по модулю 42 будет 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.

Свойство 5. Если (а,т) = 1 и х пробегает приведенную систему вычетов по модулю т, то ах также будет пробегать приведенную систему вычетов по мо­дулю т.