Системы вычетов

Системы вычетов

Системы вычетов

По этой ссылке вы найдёте полный курс лекций по математике:

Решение задач по математике

Как показано в §5, отношение сравнимости по модулю т обладает свойствами рефлексивности, симметричности и транзитивности; поэтому оно является отношением эквивалентности Возьмем произвольное целое число а. Обозначим через о множество чисел, сравнимых с а по модулю т: Пусть . Пусть теперь . И так далее. Процесс будет длиться до тех пор, пока построенные множества не будут покрывать все множество целых чисел.

При этом возникает разбиение2> множества Z на множества а. Ь, с,..которые называют классами вычетов по модулю m; каждое число, входяшее в какой-нибудь из классов, называется вычетом этого класса. Число классов вычетов по модулю т равно т. Действительно, остаток отделения целого числа на т принимает одно из значений т - 2 или т - 1 и поэтому каждое из чисел попадает в один из классов 01, количество которых равно т. Взяв по одному числу из каждого класса вычетов получим систему представителей классов вычетов, или полную систему вычетов по модулю т. Системы вычетов Пример 1.

Различные полные системы вычетов по модулю 7: Лемма 3. Числа , хт образуют полную систему вычетов по модулю т тогда и только тогда, когда они попарно не сравнимы по модулю т. Необходимость очевидна. Докажем достаточность. Если два числа не сравнимы по модулю ту то они попадают в разные классы вычетов. Так как всего классов вычетов m и рассматриваемых чисел гп, то они составляют полную систему вычетов. Лемма 4.

Пусть ,хт — полная система вычетов по модулю т, целое число а взаимно просто с т, b — произвольное целое число.

Тогда числа ахi + 6, ах2 + Ь, ..ахт -f b также образуют полную систему вычетов. Согласно лемме 3 достаточно убедиться в том, чт Предположим (для приведения к противоречию), ч OG общем определении отношения и его свойствах речь пойдет ниже — в главе LXVIII; заметим, что теория чисел является источником многих важных примеров для обшей алгебры.

Разбиение множества — это представление его в виде объединения попарно не пересекающихся подмножеств. Тогда a{xi-xj) \my и, поскольку (о, m) = 1, имеем (Xi-Xj) • m, что противоречит лемме 3. Лемма 5. Пусть х = a(modm). Тогда ( Системы вычетов м Действительно, пусть г — остаток от деления о на т. Тогда по лемме 2 Но так как х = a(mod т), при делении на m ««ело г'тамке имеет остаток г, и, следовательно, (я,т) = (г,т), откуда и вытекает требуемое.

Возможно вам будут полезны данные страницы:

Проекция вектора на ось. Скалярное произведение векторов
Кривизна плоской кривой. Радиус кривизны. Эволюта и эвольвента плоской кривой
Амиды карбоновых кислот
Проекции отрезка прямой линии

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

При m = 7 приведенная система вычетов

может выглядеть так: Системы вычетов Функцией Эйлера (р(т) называют число натуральных чисел, не превосходящих т и взаимно простьк с т. Например, . Легко видеть, что если р — простое число, Очевидно, что приведенная система вычетов по модулю т содержит чисел. Лемма 6. Пусть а взаимно просто приведенная система вычетов по модулю т.

Тогда числа ах\, ах к также образуют приведенную систему вычетов по модулю т. •4 Так как числа о и Х{ взаимно просты с т, таким же свойством обладает и их произведение ах*. В силу леммы 4 числа ах\,ах2,... принадлежат к разным классам вычетов, и, следовательно, в силу предыдущего, образуют приведенную систему вычетов.