Сравнения по данному модулю

Определение. Целые числа и называются равно остаточным

и при делении на целое число , если остаток от деления и на равны.

Пример. 1) 5 и 56 равноостаточные при делении на 7.

2)–17; 3; 15 равноостаточные при делении на 4.

Теорема 11. Для того чтобы числа и были равно остаточными при делении на целое число , необходимо и достаточно, чтобы .

Следствие. Если числа и равноостаточны при делении на и , то и равноостаточны при делении на .

Замечание Равноостаточные при делении на числа и называются также сравнимыми по модулю . Это обозначается так:

.

Эта форма записи называется еще сравнением.

Замечание Теоремы 6.2. и 6.3. можно сформулировать на языке сравнений, а именно:

Теорема 12. тогда и только тогда, когда .

Следствие Если и , то .

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

6.1. (рефлексивность).

6.2. Если , то (симметричность).

6.3. Если , , то (транзитивность)

6.4. Если и ,то .

6.5. Если и , то .

6.6. Если , то при любом натуральном .

6.7. Если и , то .

6.8. Если , то .

В теории сравнений играет важную роль теорема Ферма.

Теорема 13. (Эйлера) Пусть наибольший общий делитель чисел a и m равен 1 , где m , a , тогда (mod m ).

Теорема 14. (Ферма) Если целое число а не делится на простое число , то .