Решение сравнений и их приложения

Определение 2. Два или несколько чисел, дающие при делении на m одинаковые остатки, называются равноостаточным или сравнимыми по модулю m.
Отметим далее несколько часто используемых фактов:

1. 
   Если два целых числа a и b сравнимы по модулю m, то это можно записать различными способами : a b (mod m) или a=b+mt (где t-целое число), или a-b=mt, или (a-b) m.
   
2. 
   Если a , то и a-0 m или a 0(mod m), то есть всякое число, кратное m, сравнимо с нулём по модулю m.
   
3. 
   Любые два целых числа сравнимы по модулю 1, то есть a b (mod 1) или (a-b) 1.
   
4. 
   Если a=mq+r, то есть a при делении на m даёт остаток r, то a-r=mq или a (mod m). Таким образом, всякое целое число a всегда сравнимо с остатком r, получающимся при делении его на m.
   

Примеры.

1. 
   Доказать, что сравнение 2m+1 (m+1)²(mod m) является верным.
   

Имеем: 2m+1-(m+1)²= 2m+1 - m²-2m-1=- m², а (- m²) делится на m => наше сравнение верно.

2. 
   Доказать, что следующее сравнения являются неверными:
   

1. 
   25 (mod 10)
   

Если числа сравнимы по модулю m, то они имеют с ним один и тот же НОД.
Имеем: 4=2·2, 10=2·5, 25=5·5
НОД(4,10) = 2, НОД(25,10) = 5, следовательно наше сравнение неверно.

2. 
   (2n+1)·(2m+1) 2k (mod 6), где n, m, k – целые числа.
   

§2. Свойства сравнений

1. 
   Свойства сравнений, не зависящие от модуля.
   

Многие свойства сравнений аналогичны свойствам равенств.

1. 
   Отношение a b (mod m) является отношением эквивалент­ности, т. е. удовлетворяет требованиям:
   

а) рефлексивности: a a (mod m) (всякое целое число a срав­нимо с самим собой по модулю m);
в) симметричности: если a b (mod m), то и b a (mod m);
с) транзитивности: если a b (mod m), а b с (mod m), то a с (mod m).

2. 
   Сравнения no одному и тому же модулю можно почленно складывать, то есть если a b (mod m), c (mod m), то a+c b+d (mod m).