Приведенная система вычетов
Согласно (п. 3, Свойство 6) числа одного и того же класса по модулю т имеют с модулем один и тот же наибольший общий делитель. Особенно важны классы, для которых этот делитель равен единице, т.
е. классы, содержащие числа, взаимно простые с модулем.Взяв от каждого такого класса по одному вычету получим приведенную систему вычетов по модулю m. Приведенную систему вычетов, следовательно, можно составить из чисел полной системы, взаимно простых с модулем. Обыкновенно приведенную систему вычетов выделяют из системы наименьших неотрицательных вычетов: 0, 1, ..., т - 1. Так как среди этих чисел число взаимно простых с m есть j(m), то число чисел приведенной системы, равно как и число классов, содержащих числа взаимно простые с модулем, есть j(m).
Пример: Приведенная система вычетов по модулю 42 будет
1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.
Теорема 1: Любые j(m) чисел, попарно несравнимые по модулю m и взаимно простые с модулем, образуют приведенную систему вычетов по модулю m.
Доказательство: Будучи несравнимыми и взаимно простыми с модулем, эти числа тем самым принадлежат к различным классам, содержащим числа, взаимно простые с модулем, а так как их j(m), т.е. столько же, сколько и классов указанного вида, то в каждый класс наверно попадет по одному числу.
Теорема 2: Если (а, m) = 1 и x пробегает приведенную систему вычетов по модулю m, то ах тоже пробегает приведенную систему вычетов по модулю m.
Доказательство: Чисел ах будет столько же, сколько и чисел x, т. е. j(m). Согласно (Теорема 1) остается, следовательно, только показать, что числа ах по модулю т несравнимы и взаимно просты с модулем. Но первое доказано в (п. 4, Теорема 2) для чисел более общего вида ах + b, второе же следует из (а, m) = 1, (x, m) = 1. 6