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

Доказательство.
По условию 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.

3. 
   Два сравнения по одному и тому же модулю можно почленно вычитать одно из другого, то есть если 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).

4. 
   (следствие свойств 1, 2, 3). К обеим частям сравнения можно прибавлять одно и то же целое число.
   

Доказательство.
Пусть a b (mod m) и k –любое целое число. По свойству рефлексиности
k=k (mod m), а согласно свойствам 2 и 3 имеем a+k b+k (mod m).

5. 
   Сравнения по одному и тому же модулю можно почленно перемножать, то есть если 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 — целое неотрицательное число, то a^s b^s (mod m).

Примеры.

1. 
   Найти остаток от деления на 3 числа: А= - ·
   

Решение: очевидно 13 1 (mod 3)
2 -1 (mod 3)
5 -1 (mod 3), тогда
- · 1-1 0 (mod 13)
Ответ: искомый остаток равен нулю, и А делится на 3.

2. 
   Доказать, что 1 + 13, если х=3n+1 (n=0,1,2,…).
   

Решение:
Докажем, что 1+ 0(mod13) или 1+ 0(mod 13)
1+ =1+ 1+ =
= 1+
Так как 27 1 (mod 13), то 1+ 1+1·3+1·9 (mod 13).
ч.т.д.
3. Найдём остаток при делении с остатком числа на 24.
Имеем: 1 (mod 24), поэтому
1 (mod 24)
Прибавляя к обеим частям сравнения по 55, получаем:
(mod 24).
Имеем: (mod 24), поэтому
(mod 24) при любом k є N.
Следовательно (mod 24). Поскольку (-8) 16(mod 24), искомым остатком является 16.

6. 
   Обе части сравнения можно умножать на одно и то же це­лое число.
   

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

7. 
   Если a b (mod т) и т n, то a b (mod п)
   

Доказательство.
Так как a b (mod т), то (а — b) т. А так как т n, то в силу транзитивности отношения делимости (а — b n), то есть а b (mod n).