Числовые сравнения
Введем специальное бинарное отношение на множестве целых чисел.
Определение 13.12. Пусть
и
.
Тогда говорят, что два целых числа
и
сравнимы по модулю
,
если
.
Обозначение:
.
Числа
и
называются соответственно левой и
правой частью сравнения.
Лемма 13.19. Если , то числа имеют одинаковые остатки при делении на число , т.е., являются равноостаточными. Равноостаточность является одновременно и признаком сравнимости.
Доказательство. Тривиальное.
Лемма 13.20. Условие сравнимости
эквивалентно условию
,
где
есть некоторое целое число.
Доказательство. Тривиальное.
Лемма 13.21. Бинарное отношение сравнимости на множестве всех целых чисел является отношением эквивалентности.
Доказательство. Очевидно, что
и если
,
то
.
Поэтому докажем транзитивность отношения.
Пусть
и
,
тогда по лемме 13.20
и
для некоторых
.
Отсюда получаем, что
,
.
Значит,
.
Рассмотрим свойства числовых
сравнений. Пусть
и
.
Тогда
1.
;
2.
;
3.
;
4.
;
5.
;
6.
Числа из одной части сравнения можно
переносить в другую часть с изменением
знака. Так, если
,
то
;
7.
Если
,
и
причем
,
то
;
8.
Если
,
то
;
9.
Если
,
то
;
10.
Если
и
,
,
,
то
;
11.
Если
и
,
то
;
12.
Если
,
то
;
13. Если какая-то часть сравнения и модуль делятся на некоторое число, то другая часть должна делиться на это число.
14.
Если
,
то
.
Доказательства этих свойств
достаточно простые, основанные на
определении и леммах 13.19 и 13.20. Докажем,
например, свойство 7
.
Если
,
и
,
то
,
.
Значит,
.
Тогда по первому свойству взаимно
простых чисел, так как
,
,
т.е.,
,
что и требовалось.
Вновь пусть
и
.
По лемме 13.21 бинарное отношение сравнимости
есть отношение эквивалентности на
множестве
,
поэтому это множество распадается на
классы эквивалентности, т.е., на классы
сравнимых между собой чисел. В силу
леммы 13.19 таких классов будет ровно
,
ибо при делении на число
будет ровно такое количество различных
остатков.
Определение 13.13. Элемент класса эквивалентности по модулю называется вычетом по модулю .
Таким образом, можно говорить о
классах вычетов по модулю
.
Введем обозначение. Класс чисел,
содержащий остаток
обозначим через
.
И рассмотрим множество таких классов,
которое обозначим через
.
Именно
.
На множестве введем две бинарные алгебраические операции: сложение классов и их умножение.
Пусть для любых
и
.
Черта над суммой и произведением означает
эти числа заменяются на соответствующие
остатки от деления на
.
Надо сказать, что любое число из класса
вычетов может представлять этот класс.
При этом операции, представленные выше,
определены корректно. В самом деле,
пусть
,
,
т.е.,
,
.
Тогда по первому свойству сравнений
получаем, что
.
А это значит, что
.
Таким образом, сумма классов не зависит
от выбора представителей классов.
Аналогично и
на основе второго свойства сравнений.
Теорема 13.7. Тройка
есть коммутативное кольцо с единицей.
Доказательство. В совокупности аксиом об аддитивной группе кольца можно утверждать, что операция алгебраична и ассоциативна. Последнее следует из выкладки:
.
По аналогии доказывается коммутативность
сложения. Нейтральным элементом будет
класс
,
а противоположным для
является класс
.
Операция умножения также алгебраична
и ассоциативна. В предыдущей выкладке
стоит лишь заменить знак сложения на
знак умножения. Умножение также
коммутативно. Роль единицы играет класс
.
Остается проверить выполнимость
дистрибутивного закона. Имеем
.
Теорема доказана.
Следствие 1. Если
–
число составное, то кольцо имеет делители
нуля. В самои деле, если
,
где
,
но
и
.
Следствие 2. Если
– простое, то
– поле, называемое полем классов вычетов.
Действительно, если
,
то
.
Значит, по линейному представлению НОД
получим, что для некоторых целых
и
.
На языке классов это означает, что
,
т.е., обратным к ненулевому классу
оказывается класс
.
Что и требовалось. Это доставляет пример
конечного поля.
Пример 13.16. Пусть
.
Зададим таблицы Кэли для операций в
кольце
.
Для простоты записи откажемся от черточек
при изображении классов.
* |
0 |
1 |
2 |
3 |
4 |
5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
2 |
3 |
4 |
5 |
2 |
0 |
2 |
4 |
0 |
2 |
4 |
3 |
0 |
3 |
0 |
3 |
0 |
3 |
4 |
0 |
4 |
2 |
0 |
4 |
2 |
5 |
0 |
5 |
4 |
3 |
2 |
1 |
+ |
0 |
1 |
2 |
3 |
4 |
5 |
0 |
0 |
1 |
2 |
3 |
4 |
5 |
1 |
1 |
2 |
3 |
4 |
5 |
0 |
2 |
2 |
3 |
4 |
5 |
0 |
1 |
3 |
3 |
4 |
5 |
0 |
1 |
2 |
4 |
4 |
5 |
0 |
1 |
2 |
3 |
5 |
5 |
0 |
1 |
2 |
3 |
4 |
Определение 13.14. Система чисел, взятых по одному из каждого класса вычетов по модулю , называется полной системой вычетов по модулю (ПСВ).
Пример 13.17. Пусть , тогда системы
и
являются полными системами вычетов по модулю 6.
Обычно используются системы наименьших неотрицательных вычетов, а также системы вычетов наименьших по абсолютной величине. Именно по модулю соответственно:
и при
или
,
при
.
Лемма 13.22. Любая система целых чисел попарно не сравнимых между собой по модулю образует полную систему вычетов по модулю .
Доказательство. Очевидно.
Лемма 13.23. Если
пробегает ПСВ по модулю
,
то
тоже пробегает ПСВ по модулю
,
если
,
при любом целом
.
Доказательство. Ясно, что
указанное выражение принимает
значений. Эти значения попарно не
сравнимы между собой по модулю
.
Действительно, если при
тем
не менее
,
то тогда
.
Так как
,
то по свойству 7
сравнений получили бы
,
что приводит к противоречию. Значит, на
основе предыдущей леммы заключаем, что
тоже пробегает ПСВ по модулю
.
Легко видеть, что числа одно класса вычетов по модулю имеют один и тот же НОД с (свойство 14 сравнений). Поэтому, если такой НОД равен единице, то можно
говорить о классе вычетов взаимно простом с модулем.
Определение 13.15. Система чисел, взятых по одному из каждого класса вычетов по модулю взаимно простого с , называется приведенной системой вычетов по модулю (ПрСВ).
Приведенную систему вычетов можно
составить из вычетов полной системы,
взяв из нее только те вычеты, которые
взаимно просты с модулем. Например, из
системынаименьших неотрицательных
вычетов. Тогда становится ясным, что
количество чисев в ПРСВ по модулю
равно
.
Пример 13.18. Если
,
то ПрСВ по модулю 12 есть
.
Лемма 13.24. Система целых чисел попарно не сравнимых между собой по модулю и взаимно простых с образует приведенную систему вычетов по модулю .
Доказательство. Очевидно.
Лемма 13.25. Если
и
пробегает приведенную систему вычетов
по модулю
,
то
тоже пробегает приведенную систему
вычетов по модулю
.
Доказательство. Действительно, чисел в системе будет и они попарно не сравнимы по модулю . Ибо, если , а , то ввиду условия можно сократить обе части сравнения на общий множитель, что дает . Противоречие доказывает лемму.
Теорема 13.8 (Эйлера).
Пусть
.
Тогда
.
Доказательство. Пусть
пробегает приведенную систему наименьших
неотрицательных вычетов по модулю
:
.
Тогда в силу леммы 13.25
пробегает такую же систему
,
но, вообще говоря, в ином порядке. Имеем
,
,
. . . . . . . .
.
Перемножим почленно сравнения и находим
.
Теперь можно разделить обе части
получившегося сравнения на общую
величину
,
что и дает утверждение теоремы:
.
Следствие 1. Если , – простое число, то в условиях теоремы получаем, что
.
Этот результат называется малой теоремой Ферма.
Следствие 2. Избавляясь от условия взаимной простоты в формулировке, малую теорему Ферма можно записать в виде
.
Это сравнение справедливо и при
.