Примеры. Доказать, что сравнение 2m+1(m+1)²(mod m) является верным.
Имеем: 2m+1-(m+1)²= 2m+1 - m²-2m-1=- m², а (- m²) делится на m => наше сравнение верно.
Доказать, что следующее сравнения являются неверными:
25 (mod 10)
Если числа сравнимы по модулю m, то они имеют с ним один и тот же НОД.
Имеем: 4=2·2, 10=2·5, 25=5·5
НОД(4,10) = 2, НОД(25,10) = 5, следовательно наше сравнение неверно.
(2n+1)·(2m+1) 2k (mod 6), где n, m, k – целые числа.
Многие свойства сравнений аналогичны свойствам равенств.
Отношение 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).
Сравнения no одному и тому же модулю можно почленно складывать, то есть если a b (mod m), c (mod m), то a+c b+d (mod m).
Доказательство._По_условию_m/(a-b)_и_m/_(c-d)._Следовательно,_m/(a-b)+(c-d),_m/(a+c)-(b+d)_=>_a+c_b+d_(mod_m).__Примеры.'>Доказательство. По условию m/(a-b) и m/ (c-d). Следовательно, m/(a-b)+(c-d), m/(a+c)-(b+d) => a+c b+d (mod m).
Примеры. Найти остаток при делении на 13.
Решение: -1 (mod 13) и 1 (mod 13), тогда (-1)+1 0 (mod 13), то есть остаток от деления на 13 равен 0.
Два сравнения по одному и тому же модулю можно почленно вычитать одно из другого, то есть если a b (mod m), c (mod m), то
a-c b-d (mod m).
Доказательство. По условию m/(a-b) и m/(c-d). Следовательно, m/(a-b)-(c-d), m/(a-c)-(b-d) => (a-c) b-d (mod m).
(следствие свойств 1, 2, 3). К обеим частям сравнения можно прибавлять одно и то же целое число.
Доказательство. Пусть a b (mod m) и k –любое целое число. По свойству рефлексиности
k=k (mod m), а согласно свойствам 2 и 3 имеем a+k b+k (mod m).
Сравнения по одному и тому же модулю можно почленно перемножать, то есть если a b (mod m), c (mod m), то
a·c·d (mod m).
Доказательство. По условию, a-b є mz, c-d є mz. Следовательно a·c-b·d = (a·c - b·c)+(b·c- b·d)=(a-b)·c+b·(c-d) є mz, то есть a·c·d (mod m).
Следствие. Обе части сравнения можно возводить в одну и ту же целую неотрицательную степень: если а b (mod т) и s — целое неотрицательное число, то as bs (mod m).
