§ 2. ПОЛНАЯ СИСТЕМА ВЫЧЕТОВ

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

Согласно свойству 1.1, каждый класс вычетов по модулю однозначно определяется любым принадлежащим ему числом этот класс является множеством всех чисел вида т. е. является множеством

Класс вычетов по модулю , содержащий число а, т. е. совокупность всех целых чисел b таких, что обозначается просто через a :

Любое число, принадлежащее классу вычетов a , называется представителем этого класса.

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

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

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

Всюду ниже запись будет означать, что числа а и — взаимно простые.

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

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

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

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

Аддитивная группа классов вычетов.

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

Определим операции — на множестве классов вычетов следующим образом:

Согласно свойствам 1.4 и 1.5 сравнений, отношение сравнимости на множестве Z является конгруэнцией относительно операций сложения в Z и операций перехода к противоположному элементу.

Таким образом, любым двум классам независимо от выбора в них представителей а, b однозначно соответствует класс , являющийся их суммой. Аналогично, класс — не зависит от выбора представителя а. Так как сложение целых чисел коммутативно и ассоциативно, то коммутативно и ассоциативно сложение классов вычетов, т. е. для любых

Класс вычетов является нейтральным относительно сложения, т. е. для любого класса вычетов

Далее, классы являются взаимно противоположными, т. е.

Таким образом, имеет место следующая теорема.

ТЕОРЕМА 2.3. Алгебра является группой. Эта группа является фактор-группой группы по подгруппе

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

Кольцо классов вычетов.

На множестве классов вычетов по модулю m определим операцию умножения следующим образом:

Согласно свойству 1.5 сравнений, отношение сравнимости по модулю на Z является конгруэнцией относительно операции умножения на Z. Таким образом, каждым двум классам вычетов независимо от выбора в них представителей а, b однозначно ставится в соответствие класс вычетов являющийся их произведением.

Так как определение операций сложения и умножения классов вычетов сводится к соответствующим операциям над числами из классов вычетов, то при этом сохраняются законы сложения и умножения этих операций, в частности законы коммутативности, ассоциативности и дистрибутивности:

Кроме того, класс вычетов является нейтральным элементом относительно умножения:

Таким образом, верна следующая теорема.

ТЕОРЕМА 2.4. Алгебра является коммутативным кольцом.

ОПРЕДЕЛЕНИЕ. Кольцо называется кольцом классов вычетов по модулю .