278

ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ

извола, которым часто удаётся воспользоваться для упрощения рас-

Чётов (например, для замены больших чисел значительно меньшини).

В теоретических применениях понятия полной системы вычетов

важную роль играет следующая

Теорема З. Если числа а и т взаимно просты и в выратсе-

нин ax-l—b число х пробегает ПОЛНУЮ систему вычетов по мо-

дулю т, то н получаемые значения этого выраэюения образуют

нояную систему вычетов по модулю т.

Так как число получаемых значений выражения равно т,

то для того, чтобы убедиться, что они образуют полную систему

вычетов по модулю т, достаточно показать, что все они принадле-

жат разным классам по модулю т. Но если бы для каких-либо двух

чисел х, и х.» принадлежащих разным классам по модулю т, мы имели

ахт (tnod т).

то отсюда следовало бы:

ах1 (mod т);

так как а взаимно просто с т, то, как мы знаем, обе части сравне-

кия можно разделить на а; это дает:

(mod т),

что неверно. Таким образом, теорема З доказана. Скоро мы встре-

тимся с её важными применениями.

Мы уже знаем, что все числа, принадлежащие одному и тому же

классу, имеют с модулем одних и тех же общих делителей и, зна-

чит, — одного и того же наибольшего общего делителя. В частности,

если одно из чисел данного класса взаимно просто с модулем, то

так же обстоит дело и для всех чисел данного класса. Мы можем

поэтому говорить о кла сс а х, взаимно простых с модулем. Группа

чисел, содержащая по одному представителю от каждого класса,

взаимно простого с модулем, называется приведённой (в отличие от

полной) системой вычетов по данному модулю. Самый простой спо-

соб получить приведённую систему вычетов по модулю т состоит,

очевидно, в том, чтобы отобрать в ряду чисел

представляющих собою полную систему вычетов по модулю т, те,

которые взаимно просты с т. Таким образом, число классов, вза-

имно простых с т (или, что то же, число членов любой приведен-

ной системы вычетов по модулю т), равно числу натуральных

чисел. не превосходящих т и взаимно простых с т. Эго число,

зависящее, очевидно, только от т, и обозначаемое через ф (т), есть

одна из важнейших арифметических функций натурального числа ш.

Мы увидим дальше, как просто может быть найдено значение этой

функции. если извескно разложение числа т на простые множители.