МЕТОЛ СРАВНЕНИЙ

279

Для приведённой системы вычетов имеет место следующее важ-

ное предложение, аналогичное теореме 3 для полной системы

вычетов:

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

разсении ах число х пробегает какую-либо приведённую систему

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

ния образуют приведённую cttcme„wy вычетов по модулю т.

Следует обратить внимание на то, что фигурирующее в теореме З

произвольное число Ь в теореме 4 обязательно равно нулю; это

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

значительно шире того свойства приведённых систем, которое выра-

жается теоремой 4.

Для доказательства теоремы 4 достаточно заметить, что, когда х

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

получающиеся при этом ф (т) значени произведения ах все взаимно

просты с т и, как было показано п и доказательстве теоремы 3,

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

Теорема 4 позволяет легко доказать одно интересное и важное

предложение, найденное Эйлером. Пусть числа а и т взаимно просты

и пусть

(3)

где для краткости положено ф (т) — любая приведённая система

вычетов по модулю ш. В силу теоремы 4 числа

arv ar,» .

(4)

также представляют собою приведённую систему вычетов по мо-

дулю т. Таким образом, каждое из чисел (4) сравнимо по модулю т

с одним из чисел (З), т. е.

ar, = ri1

(tnod т),

где ряд индексов П, 4, . , is есть расположенный только в другом

порядке ряд чисел 1, 2, ... ,

s. Перемножая эти сравнения по-

членно, мы находим:

rs—qri2 •

rs (mod т).

Так как каждое взаимно просто с т, то и произведение их

взаимно просто с т , и, следовательно, мы можем разделить на это

произведение обе части последнего сравнения. Это и приводит нас

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

с т, то

а? (tnod т).