§ 5. Приведенная система вычетов

a. Согласно f, § 3 числа одного и того же класса по модулю имеют с модулем один и тот же общий наибольший делитель. Особенно важны классы, для которых этот делитель равен единице, т. е. классы, содержащие числа, взаимно простые с модулем.

Взяв от каждого такого класса по одному вычету, получим приведенную систему вычетов по модулю т. Приведенную систему вычетов, следовательно, можно составить из чисел полной системы, взаимно простых с модулем. Обыкновенно приведенную систему вычетов выделяют из системы наименьших неотрицательных вычетов: Так как среди этих чисел число взаимно простых с есть , то число чисел приведенной системы, равно как и число классов, содержащих числа, взаимно простые с модулем, есть

Пример. Приведенная система вычетов по модулю 42 будет

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

Действительно, будучи несравнимыми и взаимьо простыми с модулем, эти числа тем самым принадлежат к различным классам, содержащим числа, взаимно простые с модулем, а так как их т. е. столько же, сколько и классов указанного вида, то в каждый класс наверно попадет по одному числу.

с. Если пробегает приведенную сццстему вычетов по модулю , то тоже пробегает приведенную систему вычетов по модулю .

Действительно, чисел будет столько же, сколько и чисел . Согласно b остается, следоватгельно, только показать, что числа по модулю несравнимы и взаимно просты с модулем. Но первое доказало в d, § 4 для чисел более общего вида второе следует из