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

§1. Сравнение по модулю
Пусть z-кольцо целых чисел, m-фиксированное целое число и m·z-множество всех целых чисел, кратных m.
Определение 1. Два целых числа a и b называют сравнимыми по модулю m, если m делит a-b.
Если числа a и b сравнимы по модулю m, то пишут a b (mod m).
Условие a b (mod m) означает, что a-b делится на m.
a b (mod m)↔(a-b) m

Определим, что отношение сравнимости по модулю m совпадает с отношением сравнимости по модулю (-m) (делимость на m равносильно делимости на –m). Поэтому, не теряя общности, можно считать, что m>0.

Примеры.

1. 
   m=3; 8 5(mod 3), так как 8-5=3 и 3 делится на 3
   
2. 
   m=5; 12 (mod 5), так как 12-2=10 и 10 делится на 5
   
3. 
   m=2; 3 7(mod 2), так как 3-7=-4 и -4 делится на 2
   
4. 
   m=5; 11 (mod 5), так как 11-3=8, а 8 не делится на 5
   

Теорема. (признак сравнимости дух чисел по модулю m): Два целых числа a и b сравнимы по модулю m тогда и только тогда, когда a и b имеют одинаковые остатки при делении на m.
Доказательство.
Пусть остатки при делении a и b на m равны, то есть a=mq₁+r, (1)
b=mq₂+r, (2)
где 0≤r≥m.
Вычтем (2) из (1), получим a-b= m(q₁- q₂), то есть a-b m или a b (mod m).
Обратно, пусть a b (mod m). Это означает, что a-b m или a-b=mt, t z (3)
Разделим b на m; получим b=mq+r в (3), будем иметь a=m(q+t)+r, то есть при делении a на m получается тот же остаток, что и при делении b на m.

Примеры.

1. 
   Имеем -5 23(mod 4), так как при делении с остатком на 4 числа -5 и 23 имеют одинаковые остатки
   

-5=4·(-2)+3
23=4·5+3

2. 
   Числа 24 и 10 не сравнимы по модулю 3: 24 10(mod 3), поскольку при делении с остатком на 3 они дают разные остатки.
   

24=3·8+0
10=3·3+1