Приведенная система вычетов
Определение Числа одного и того же класса по модулю М имеют с модулем один и тот же общий наибольший делитель. Особенно важны классы, для которых этот делитель равен единице, т.е. классы, содержащие числа, взаимно простые с модулем. Взяв от каждого такого класса по одному вычету, получим приведенную систему вычетов по модулю М. Приведенную систему вычетов, следовательно, можно составить из чисел полной системы, взаимно простых с модулем. Обыкновенно приведенную систему вычетов выделяют из системы наименьших неотрицательных вычетов: 0,1, . . ., М-1. Так как среди этих чисел число взаимно простых с М есть f(М), то число чисел приведенной системы, равно как и число классов, содержащих числа, взаимно простые с модулем, есть f(М). Пример Пример. Приведенная система вычетов по модулю 42 будет 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.