§ 3. ПРИВЕДЕННАЯ СИСТЕМА ВЫЧЕТОВ

Приведенная система вычетов.

Пусть — любое положительное число. Обозначим через число положительных целых чисел, не превосходящих и взаимно простых с . Наибольший общий делитель целых чисел а, b, являющийся натуральным числом, будем обозначать через

ПРЕДЛОЖЕНИЕ 3.1. Все числа из фиксированного класса вычетов имеют с один и тот же наибольший общий делитель, равный .

Доказательство. Если b есть любое число класса вычетов , то где q — некоторое целое число. Отсюда в силу предложения 11.3.1 следует, что .

Следовательно, зависит только от класса вычетов и не зависит от выбора представителя а в этом классе.

В частности, если , то класс называется классом вычетов, взаимно простым с модулем .

ПРЕДЛОЖЕНИЕ 3.2. Число классов вычетов, взаимно простых с , равно .

Доказательство. Из полной системы вычетов по модулю

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

В силу предложения 3.1 классы вычетов

взаимно простые с модулем . Всякий другой класс, не входящий в (1), не взаимно простой с модулем , так как содержит элемент множества Классы, входящие в систему (1), различны. Следовательно, число классов, взаимно простых с , равно

ОПРЕДЕЛЕНИЕ. Приведенной системой вычетов по модулю называется совокупность целых чисел, содержащая по одному представителю из каждого класса вычетов, взаимно простого с .

ПРЕДЛОЖЕНИЕ 3.3. Любая совокупность чисел взаимно простых с и попарно несравнимых по модулю , есть приведенная система вычетов по модулю .

Доказательство. Пусть М есть совокупность чисел, взаимно простых с и попарно несравнимых по модулю . Тогда эти числа принадлежат к различным классам вычетов. Поэтому множество М содержит по одному представителю из каждого класса вычетов, взаимно простого с модулем . Следовательно, М есть приведенная система вычетов по модулю .

ПРЕДЛОЖЕНИЕ 3.4. Пусть а — целое число, взаимно простое с , и — приведенная система вычетов по модулю . Тогда совокупность тоже есть приведенная система вычетов по модулю .

Доказательство. Ввиду предложения 3.3 достаточно показать, что числа совокупности попарно несравнимы по модулю .

Действительно, если при , то ввиду условия , что невозможно, так как, по условию предложения, — различные элементы приведенной системы вычетов по модулю .