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



бет2/14
Дата09.06.2022
өлшемі131,78 Kb.
#36581
түріРешение
1   2   3   4   5   6   7   8   9   ...   14
Байланысты:
reshenie sravnenii i ih prilozheniya 0


§1. Сравнение по модулю
Пусть z-кольцо целых чисел, m-фиксированное целое число и m·z-множество всех целых чисел, кратных m.
Определение 1. Два целых числа a и b называют сравнимыми по модулю m, если m делит a-b.
Если числа a и b сравнимы по модулю m, то пишут ab (mod m).
Условие ab (mod m) означает, что a-b делится на m.
ab (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 или ab (mod m).
Обратно, пусть ab (mod m). Это означает, что a-b m или a-b=mt, tz (3)
Разделим b на m; получим b=mq+r в (3), будем иметь a=m(q+t)+r, то есть при делении a на m получается тот же остаток, что и при делении b на m.

Примеры.

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

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

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

24=3·8+0
10=3·3+1
Определение 2. Два или несколько чисел, дающие при делении на m одинаковые остатки, называются равноостаточным или сравнимыми по модулю m.
Отметим далее несколько часто используемых фактов:

  1. Если два целых числа a и b сравнимы по модулю m, то это можно записать различными способами : ab (mod m) или a=b+mt (где t-целое число), или a-b=mt, или (a-b) m.

  2. Если a, то и a-0m или a0(mod m), то есть всякое число, кратное m, сравнимо с нулём по модулю m.

  3. Любые два целых числа сравнимы по модулю 1, то есть ab (mod 1) или (a-b) 1.

  4. Если a=mq+r, то есть a при делении на m даёт остаток r, то a-r=mq или a (mod m). Таким образом, всякое целое число a всегда сравнимо с остатком r, получающимся при делении его на m.



Достарыңызбен бөлісу:
1   2   3   4   5   6   7   8   9   ...   14




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет