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

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

Тогда:

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

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

Тогда

То есть .

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

, так как:

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

.

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

5. .

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

6. Если , то .

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

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

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

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

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

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

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

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

Примеры.

1. . Но .

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

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

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

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

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

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

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

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

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

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

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

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

Примеры.

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

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

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

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

Пример. Для числа существует меньших его и взаимно простых с ним чисел , поэтому .

Первые 99 значений функции Эйлера:

Таблица 6

Теорема. Если натуральное число имеет разложение на простые множители , то функция Эйлера равна:

Пример. Вычислим функцию Эйлера .

Мультипликативная функция — функция , в которой для любых взаимно-простых справедливо: .

Очевидно, что функция Эйлера — мультипликативная.

Теорема Эйлера. Для любого модуля и любого числа , взаимнопростого с числом , имеет место формула Эйлера: .

Пример. Найти остаток от деления числа на . Заметим, что числа 174 и 13 взаимно просты. Сначала вычислим значение функции Эйлера от делителя:

Затем разделим показатель степени 249 на с остатком: .

Тогда .

По теореме Эйлера , тогда , откуда , и таким образом , получаем и так как , то с учётом , получим . , то есть . Окончательно получаем: , то есть остаток при делении равен 5.

Теорема. Пусть — главный идеал кольца . Тогда множество классов вычетов по модулю образуют коммутативное кольцо с 1 с операциями сложения и умножения:

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

Ранее было доказано, что сумма и произведение классов вычетов не зависят от выбора представителей классов, поэтому кольцо коммутативно:

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

Пример. Кольцо.

Пример.

(или ) — кольцо классов вычетов по модулю 3.

.

.

.

Противоположный это . Действительно, .