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

278 ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ иэвола, которым часто удаётся воспользоваться для упрощения рас­ чётов (например, для замены больших чисел значительно меньшими). В теоретических применениях понятия полной системы вычетов важную роль играет следующая Т е о р е м а 3. Если числа а и т взаимно просты и в выраже­ нии ах-\-Ь число х пробегает полную систему вычетов по мо­ дулю те, то и получаемые значения этого выражения образуют полную систему вычетов по модулю т. Так как число получаемых значений выражения ах-\-Ь равно те, то для того, чтобы убедиться, что они образуют полную систему вычетов по модулю те, достаточно показать, что все они принадле­ жат разным классам по модулю т. Но если бы для каких-либо двух чисел х и лг , принадлежащих разным классам по модулю те, мы имели х 2 ах -\-Ь = ах -\- Ъ (mod те). х г то отсюда следовало бы: ах = ах% (mod те); 1 так как а взаимно просто с те, то, как мы знаем, обе части сравне­ ния можно разделить на а; это даёт: х = х х л (mod те), что неверно. Таким образом, теорема 3 доказана. Скоро мы встре­ тимся с её важными применениями. Мы уже знаем, что все числа, принадлежащие одному и тому же классу, имеют с модулем одних и тех же общих делителей и, зна­ ч и т , — одного и того же наибольшего общего делителя. В частности, если одно из чисел данного класса взаимно просто с модулем, то так же обстоит дело и для в с е х чисел данного класса. Мы можем поэтому говорить о к л а с с а х , взаимно простых с модулем. Группа чисел, содержащая по одному представителю от каждого класса, взаимно простого с модулем, называется приведённой (в отличие от полной) системой вычетов по данному модулю. Самый простой спо­ соб получить приведённую систему вычетов по модулю те состоит, очевидно, в том, чтобы отобрать в ряду чисел 1, 2, . • . , т, представляющих собою полную систему вычетов по модулю те, те, которые взаимно просты с те. Таким образом, число классов, вза­ имно простых с те (или, что то же, число членов любой приведён­ ной системы вычетов по модулю те), равно числу натуральных чисел, не превосходящих те и взаимно простых с те. Это число, зависящее, очевидно, только от те, и обозначаемое через 9 (те), есть одна из важнейших арифметических функций натурального числа те. Мы увидим дальше, как просто может быть найдено значение этой функции, если изрестно разложение числа те на простые множители.