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

Если рассмотреть свойства сравнений 1) – 3) из пункта 1.1, то можно сказать, что множество целых чисел Z состоит из объединения непересекающихся подмножеств, каждое из которых состоит из чисел, попарно сравнимых между собой. Данные подмножества называются классами вычетов по модулю m, при этом элементы каждого подмножества называются вычетами данного класса.
Обозначим a – класс вычетов, содержащий целое число a. Следовательно, a=b тогда и только тогда, когда a≡b mod m.
Каждое число a∈Z можно представить в виде:
a=mq+r,
где 0≤rm, q, r∈Z. Таким образом, числа a и r лежат в одном классе вычетов и, следовательно, любой класс вычетов содержит целое число r∈0, m. Значит, число классов вычетов по модулю m не превосходит m.
С другой стороны, каждое из чисел 0, 1, 2, …, m-1 лежит в некотором классе вычетов и эти классы различны, так как разность любых двух указанных чисел не делится нацело на m.
Таким образом, существует ровно m классов вычетов по модулю m, каждый из которых содержит единственное челое число r∈0, m, называемое наименьшим неотрицательным вычетом класса. Следовательно, все классы вычетов по модулю m – это 0, 1, …, m-1.
На множестве классов вычетов по модулю m можно определить операции сложения, вычитания
a±b=a±b
и умножения
a⋅b=a⋅b.
Определение. Совокупность представителей всех классов вычетов по заданному модулю m≥2 называется полной системой вычетов по модулю m

.
Например, полную систему вычетов по модулю 5 составляют числа
-2, -1, 0, 1, 2;
0, 2, 4=22, 8=23, 16=24,
0, 1, 2, 3, 4
Также полной системой вычетов по модулю m является совокупность целых чисел -m2x≤m2. Это абсолютные наименьшие вычеты классов по модулю m. Например, для модуля m=6 полную систему вычетов образуют числа -2, -1, 0, 1, 2, 3.
Теорема 1. Любая совокупность m чисел, m≥2, попарно несравнимых по модулю m, является полной системой вычетов по модулю m.
Доказательство. Пусть M – совокупность m чисел, попарно несравнимых по модулю m. Тогда эти числа принадлежат к различным классам вычетов. Учитывая, что множество M содержит m чисел, получаем, что множество M содержит по одному представителю из каждого класса вычетов по модулю m. Теорема доказана.
Теорема 2. Пусть даны целые взаимно простые числа a, m≥2. Тогда если x пробегает полную систему вычетов по модулю m, то ax+b, где b – любое целое число, также пробегает полную систему вычетов по модулю m.
Доказательство. Пусть M – полная система вычетов. Тогда множество M1=ax+b, x∈M, так же, как и M, содержит m элементов. Если числа x1 и x2 из класса вычетов M несравнимы, то ax1+b≢ax2+b mod m. Следовательно, множество M1 есть полная система вычетов по модулю m