Материал: Ответы на экзаменационные вопросы по дискретной математике

10. Сравнения. Классы вычетов по модулю (по идеалу ). Свойства. Малая теорема Ферма. Функция Эйлера. Теорема Эйлера (теория чисел) Сравнения

Пусть — главный идеал коммутативного кольца .

Два элемента и кольца называются сравнимыми по модулю (по идеалу ), если их разность принадлежит идеалу :

Обозначение сравнения по модулю: или .

Пусть — кольцо (целых чисел). Тогда , если при делении на получаются одинаковые остатки. Действительно, пусть , тогда: .

Примеры.

1. (так как ).

2. (так как ).

Класс вычетов по модулю (по идеалу ) — множество элементов кольца, сравнимых с по модулю . Можно обозначить так: . Элемент — представитель класса вычетов .

Пример. , то есть идеал :

Лемма. Два класса вычетов и или не пересекаются, или совпадают. Иначе говоря, классы вычетов по модулю образуют разбиение кольца .

Отношение сравнимости по модулю обладает следующими свойствами:

• Свойство рефлексивности: .

• Свойство симметричности: если , то .

• Свойство транзитивности: если и , то

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

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

Пример. В предыдущем примере: , то есть идеал . Имеем лишь три класса вычетов: (обозначения ) — которые образуют полную систему вычетов по модулю 3. Ясно, что любой элемент из принадлежит лишь одному из этих классов.

Свойства сравнений

Пусть , то есть ; .

Тогда:

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

Действительно: пусть .

Тогда

То есть .

2. . (Сравнения можно перемножать.)

, так как:

3. . (К обеим частям сравнения можно прибавить одно и то же число .)

.

4. . (Следствие 2.).

5. .

Действительно, , поэтому и из предыдущего:

6. Если , то .

Действительно, , следовательно , где , то есть , то есть .

7. Если , то . (Можно одновременно разделить обе части сравнения и модуль на их общий делитель.)

Действительно, если , то , значит .

Замечание. Из не следует, что .

Сумма классов вычетов и есть класс вычетов .

Произведение классов вычетов и есть класс вычетов .

Теорема. Сумма (и разность) и произведение классов вычетов не зависят от выбора представителей классов.

Доказательство. Пусть . Тогда, используя свойства сравнений №1 и №2, получим: . Следовательно, и .

Примеры.

1. . Но .

2. 

3. Найти остаток при делении на .

, то есть остаток равен 0.

4. Найти две последние цифры числа . Для этого достаточно найти остаток при делении на ; для этого выясним остаток при делении на и на :

, то есть последние две цифры могут быть .

, значит последние две цифры могут быть только 52.

5. Доказать, что .

Надо дать 4 сравнения по модулю .

Итак , тогда по свойству №6 , где (так как числа простые), то есть .

Замечание. Приведём без доказательства ещё два полезных свойства сравнений, которые выражены следующей теоремой:

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

1. Если число не делится на простое число , то справедливо:

2. Если число и — простое число, то справедливо (здесь отсутствует требование, чтобы делилось на ):

Примеры.

1. , так как 31 — простое число.

2. , так как 541 — простое число.

Замечание. При решении задач на сравнение также удобно пользоваться функцией Эйлера.

Функция Эйлера — функция, равная количеству натуральных чисел, меньших аргумента и взаимно простых с ним. При этом полагают по определению, что число 1 взаимно просто со всеми натуральными числами, и .