12.  Сравнения и вычеты. Кольцо вычетов. Малая терема Ферма. Сравнения первой степени. Китайская теорема об остатках.

Сравнения

Зафиксируем натуральное число т => 1, которое условимся называть модулем.

Определение 1. Два целых числа а, b назовем сравнимыми по модулю т, если они при делении на т дают одинаковые остат­ки. Обозначение:

Рассмотрим простейшие свойства сравнений.

Теорема 1. Сравнения целых чисел по модулю т обладают следующими свойствами для любых а, b, с, d € Z:

(т. е.  сравнения можно почленно складывать,   вычитать  и перемножать),

6) если d есть общий делитель чисел а, b, т, то

7) если числа а, b делятся на d и d взаимно просто с т, то

Классы вычетов по модулю т

Из свойств 1) — 3) сравнений видно, что отношение сравнимо­сти целых чисел по модулю т является отношением эквивалент­ности, и, следовательно, множество целых чисел разбивается на непересекающиеся классы сравнимых по модулю m чисел. Так как различные остатки при делении на т исчерпываются числами

0,1,2,...,m-1, то получим т классов: (2) где черезобозначен класс всех чисел, которые при делении на т дают в остатке r. Очевидно, что классоднозначно определяется любым одним своим представителем, и потому в даль­нейшем классбудет обозначаться также в виде, где а — любой представитель этого класса.

Классы (2) называются классами вычетов, а их элементы — вычетами по модулю т. Из определения сравнений следует, что числа из одного класса сравнимы по модулю т, а числа из разных классов не сравнимы по модулю т, т. е.

Определение 1. Совокупность чисел, взятых по одному из каждого класса вычетов по модулю т, называется полной систе­мой вычетов по модулю т.

Примером полной системы вычетов по модулю т является множество чисел 0,1,... , m — 1. Это так называемая полная система наименъшцх неотрица­тельных вычетов.

Cледующее свойство полных систем вычетов.

Теорема 1. Если  есть полная система вычетов по модулю т, число а взаимно простое с т и b — любое целое число, то (3) есть таксисе полная система вычетов по модулю т.

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

А так как в (3) содержится т чисел, т. е. столько же чисел, сколь­ко и классов, то в (3) имеется ровно по одному представителю из каждого класса. Следовательно, (3) есть полная система вычетов по модулю т

Малая терема Ферма

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

Определение 3. Совокупность чисел, взятых по одному из всех классов, взаимно простых с модулем т, называется приве­денной системой вычетов по модулю т

Число классов, взаимно простых с модулем m, или число чи­сел в приведенной системе вычетов по модулю т, обозначают в математике через, а функцию, сопоставляющую числу т число, называют функцией Эйлера. Ясно, что есть числонатуральных чисел, не превосходящих т и взаимно про­стых с т. Например,= 1,=1,=4. Очевидно, что для простого числа р имеем:. Общее: при любом натуральном к. Для доказательства последнегоравенства достаточно заметить, что в ряду изчисел содержится ровночисел, не взаимно простых с Это— все числа, кратные р: р, 2р, Зр, ..., Приведем еще,  так называемое свой­ство мультипликативности функции Эйлера

Для любых натуральных взаимно простых чисел т, п имеет место соотношение

Отсюда, используя основную теорему арифметики, получаем общую формулу для вычисления функции Эйлера. Если число т имеет каноническое разложение

то

Теорема 2*. Если (4) есть приведенная система вычетов по модулю т и число а вза­имно просто с т, то набор чисел (5) также является приведенной системой вычетов по модулю т

Кольцо вычетов

Рассмотрим множествовсех классов вычетов по модулю . Класссостоит из всех чисел вида , где t пробегает множество Z, т. е.

Следовательно, классы вычетов по модулю та совпадают со смеж­ными классами кольца Z по его идеалу mZ.

Теорема 1.  Определение операций сложения и умножения классов вычетов по формулам

 корректно, и множествос этими операциями является

коммутативным кольцом с единицей. Это есть факторкольцо  кольца Z по его идеалу тZ.

Кольцо Z/rn называют кольцом классов вычетов по модулю т.

Опишем обратимые элементы этого кольца.

Теорема 2. Элементобратим в кольце Z/m тогда и только тогда, когда классвзаимно прост с т, т. е. (а,т) = 1.

Китайская теорема об остатках

По китайской теореме об остатках система сравненийимеет единственное решение по модулю т.