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

Пример.
Найти остаток от деления 196 на 7.
Решение:
Зная, что 196= , можно записать 196 (mod 14). Воспользуемся предыдущим свойством, 14 7, получим 196 (mod 7), то есть 196 7.

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

Доказательство.
Пусть a b (mod т) и с-целое положительное число. Тогда a-b = mt и ac-bc=mtc, или ac bc (mod mc).
Пример.
Выяснить, является ли значение выражения целым числом.
Решение:
Представим дроби в виде сравнений: 4 (mod 3)
1 (mod 9)
31 (mod 27)
Сложим почленно эти сравнения (свойство 2), получим 124 (mod 27) Мы видим, что 124 не делится целочисленно на 27, следовательно значение выражения тоже не является целым числом.

9. 
   Обе части сравнения можно разделить на их общий множитель, если он взаимно простой с модулем.
   

Пример.'>Доказательство.
Если cа cb (mod m), то есть m/c(a-b) и число с взаимно простое с m, (с,m)=1, то m делит a-b. Следовательно, a b (mod т).
Пример.
60 9 (mod 17), после деления обеих частей сравнения на 3 получим:
20 (mod 17).
Делить обе части сравнения на число, не взаимно простое с модулем, вообще говоря, нельзя, так как после деления могут получиться числа, несравнимые по данному модулю.
Пример.
8 (mod 4), но 2 (mod 4).

10. 
    Обе части сравнения и модуль можно разделить на их общий делитель.
    

Доказательство.
Если ka kb (mod km), то k (a-b) делится на km. Следовательно, a-b делится на m, то есть a b (mod т).

11. 
    Пусть Р (х) — многочлен с целыми коэффициентами, а и Ь — переменные, принимающие целые значения. Тогда если a b (mod т), то Р (а) Р (b) (mod m).