Сравнения и основные операции

Пусть есть два числа a и b, которые при делении на m дают равные остатки. Записывать это будем как a≡ b(mod m). Читается такая запись как “a сравнимо с b по модулю m”.

Примеры

9≡5(mod 4)

48≡13(mod 7)

28≡3(mod 5)

Для начала давайте скажем, что числа a и b можно представить, как a=mt+r, b=mk+r, где t и k – неполные частные от деления a и b на m соответственно, а r – остаток от деления a и b на m.

Примеры

9/4=2 ост. 1 <=> 9=4*2+1; 5/4=1 ост. 1 <=> 5=4*1+1.

48/7=6 ост. 6 <=> 48=6*7+6; 13/7=1 ост. 6 <=> 13=7*1+6.

28/5=5 ост. 3 <=> 28=5*5+3; 3/5=0 ост. 3 <=> 3=5*0+3.

Теперь скажем, какие операции мы можем и хотели бы проделывать со сравнениями.

Сложение

Пусть есть два сравнения a≡b(mod m), c≡d(mod m). Давайте продемонстрируем, что a+c≡b+d(mod m). Представим числа следующим образом

a=mt+r, b=mk +r, c=mh+q, d =mp+q.

Тогда получается a+c=mt+r+mh+q и b+d= mk+r+mp+q.

Т.к. r и q остатки от деления на m, 0≤r,q≤m-1, а значит 0≤r+ q≤2m-2. Давайте рассмотрим два случая

1) 0≤ r+q<m, получается, что a+c≡r+q(mod m), т.к. a+c=m(t+h)+r+q, где r+q остаток от деления a+c на m. Аналогично b+ d≡ r+q(mod m). Ну а раз у a+c и b+ d равные остатки от деления на m, то a+c≡b+d(mod m) ч.т.д.

2) m≤r+q≤2m-2, тогда пусть w=r+q-m, иными слова w – остаток от деления r+q на m. Получаем a+c= mt+mh+w+m ó a+c= m( t+h+1)+w, аналогично b+d=m(k+p+1)+ w, значит у a+c и b+d остаток от деления на m равен w, а значит a+c≡b+d(mod m) ч.т.д.

Ну и в итоге

a≡b(mod m), c≡d(mod m) => a+c≡b+d(mod m)

Приведем пару примеров.

9≡5(mod 4), 18≡46(mod 4) => 27≡51(mod 4)

48≡13(mod 7), 68≡40(mod 7) => 116≡53(mod 7)

28≡3(mod 5), 22≡7(mod 5) => 50≡10(mod 5)

Умножение

Пусть есть два сравнения a≡b(mod m), c≡d(mod m). Давайте продемонстрируем, что a*c≡b*d(mod m). Представим числа следующим образом

a=mt+r, b=mk +r, c=mh+q, d =mp+q.

Тогда a*c=(mt+r)(mh +q)=m²th+mtq+ mhr +rq=m(mth+tq+ hr )+rq, аналогично b*d=m( mkp+kq+pr)+rq, довольно очевидно , что m(mth+tq+hr)≡0(mod m), и m(mkp+kq+ pr)≡0(mod m) => m( mth +tq+hr)≡m(mkp+ kq+pr)(mod m), а также очевидно rq≡rq(mod m), а значит, из правила сложения получаем

m(mth+tq+hr)+rq ≡m(mkp+kq+pr)+ rq (mod m), отсюда a*c≡ b *d(mod m) ч.т.д.

Ну и в итоге

a≡b(mod m), c≡d(mod m) => a*c≡b*d(mod m)

Приведем пару примеров.

9≡5(mod 4), 18≡46(mod 4) => 162≡230(mod 4)

48≡13(mod 7), 68≡40(mod 7) => 3264≡520(mod 7)

28≡3(mod 5), 22≡7(mod 5) => 616≡21(mod 5)

Возведение в степень

Пусть есть сравнение a≡b(mod m) и число t. Давайте продемонстрируем, что a^t≡ b^t(mod m). Т.к. мы знаем, что

a≡b(mod m), c≡d(mod m) => a*c≡b*d(mod m),

то можем рассмотреть такой частный случай

a≡b(mod m), a≡b(mod m) => a² ≡b²(mod m),

затем

a≡b(mod m), a²≡b² (mod m) => a³≡b³(mod m)

ну и довольно очевидно, что продолжать это можно до бесконечности, а значит

a≡b(mod m) <=> a^t≡b^t(mod m)

ч.т.д.

Приведем несколько примеров

9≡5(mod 4) => 81≡25(mod 4)

10≡3(mod 7) => 1000≡27(mod 7)

4≡6(mod 2) => 1024≡7776(mod 2).