Решение сравнений и их приложения
жүктеу/скачать 131,78 Kb.
|
- Бұл бет үшін навигация:
- Доказательство. Пусть остатки при делении a и b на m равны, то есть a=mq₁+r, (1) b=mq₂+r, (2)
- Определение 2.
§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. Примеры. m=3; 8 5(mod 3), так как 8-5=3 и 3 делится на 3 m=5; 12 (mod 5), так как 12-2=10 и 10 делится на 5 m=2; 3 7(mod 2), так как 3-7=-4 и -4 делится на 2 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. Примеры. Имеем -523(mod 4), так как при делении с остатком на 4 числа -5 и 23 имеют одинаковые остатки -5=4·(-2)+3 23=4·5+3 Числа 24 и 10 не сравнимы по модулю 3: 2410(mod 3), поскольку при делении с остатком на 3 они дают разные остатки. 24=3·8+0 10=3·3+1 Определение 2. Два или несколько чисел, дающие при делении на m одинаковые остатки, называются равноостаточным или сравнимыми по модулю m. Отметим далее несколько часто используемых фактов: Если два целых числа a и b сравнимы по модулю m, то это можно записать различными способами : ab (mod m) или a=b+mt (где t-целое число), или a-b=mt, или (a-b) m. Если a, то и a-0m или a0(mod m), то есть всякое число, кратное m, сравнимо с нулём по модулю m. Любые два целых числа сравнимы по модулю 1, то есть ab (mod 1) или (a-b) 1. Если a=mq+r, то есть a при делении на m даёт остаток r, то a-r=mq или a (mod m). Таким образом, всякое целое число a всегда сравнимо с остатком r, получающимся при делении его на m. жүктеу/скачать 131,78 Kb. Достарыңызбен бөлісу:
|