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

МЕТОД СРАВНЕНИЙ 279 Для приведенной системы вычетов имеет место следующее важ­ ное предложение, аналогичное теореме 3 для полной системы вычетов: Т е о р е м а 4. Если числа а и т взаимно просты а если в вы­ ражении ах число х пробегает какую-либо приведённую систему вычетов по модулю т то и получаемые значения этого выраже­ ния образуют приведённую систему вычетов по модулю т. Следует обратить внимание на то, что фигурирующее в теореме 3 произвольное число Ь в теореме 4 обязательно равно нулю; это показывает, что свойство полных систем, выражаемое теоремой 3, значительно шире того свойства приведенных систем, которое выра­ жается теоремой 4. Для доказательства теоремы 4 достаточно заметить, что, когда х пробегает какую-либо приведенную вычетов по модулю т получающиеся при этом ср (т) значений произведения ах все взаимно просты с т и, как было показано при доказательстве теоремы 3, все принадлежат различным классам по модулю т. Теорема 4 позволяет легко доказать одно интересное и важное предложение, найденное Эйлером. Пусть числа awm взаимно просты и пусть % систему 9 где для краткости положено ср (т)=s — любая приведенная система вычетов пб модулю т. В силу теоремы 4 числа 9 аг 19 аГц ... , ar s (4) такжё представляют собою приведенную систему вычетов по мо­ дулю т. Таким образом, каждое из чисел (4) сравнимо по модулю т с одним из чисел (3), т. е. ar = r t h | 1 ( d/и), m o cr. z г (э где ряд индексов *„ i , . . . , i есть расположенный только в другом порядке ряд чисел 1, 2, . . . , s. Перемножая эти сравнения по­ членно, мы находим: 2 s a*< >r,r . . . г = Г{ г П =г Гъ . . . r (mod/и). Так как каждое r взаимно просто с т то и произведение их взаимно просто с т , и, следовательно, мы можем разделить на это произведение обе части последнего сравнения. Это и приводит нас к теореме Э й л е р а , утверждающей, что если а взаимно просто с /га, то vm==l (mod т). 2 в Л к $ к s t 9 a m