Алгебра. Лекция 4. Теория сравнений – теория остатков

1. Лекция 4 Теория сравнений – теория остатков

2. Числовые сравнения. Понятие сравнения

Определение 1
Целые числа a и b называются сравнимыми по
модулю m, если разность a - b делится на m
Обозначение: a b (mod m)
Примеры
5 1 (mod 6)
18 0 (mod 6)
1717 37 (mod 10)

3. Теорема 1 Следующие утверждения равносильные:

• (1) a b (mod m)
• (2) существует t ϵ Z ,что a b mt
• (3) a и b при делении на m дают одинаковые
остатки (т.е. a и b равноостаточны)

4. Доказательство

1. Докажем, что из (1) следует (2).
По определению имеем:
a b (mod m) (a b) m a b mt , t Z a b mt
2. Докажем, что из (2) следует (3). Существует t ϵ Z , что
a b mt
Разделим b на m с остатком, тогда
b mq r , 0 r m , a mt mq r m(t q) r
Следовательно, a и b имеют одинаковые остатки
3. Докажем, что из (3) следует (1)
a и b при делении на m имеют одинаковые остатки:
a mq1 r и b mq 2 r
Тогда a b m(q1 q2 ) m, т.е. a b (mod m)

5.

Определение 2
Числа a и b называются сравнимыми по
модулю m, если они имеют одинаковые
остатки при делении на m
Определение 3
Числа a и b называются сравнимыми по
модулю m, если a от b отличается на число,
кратное m

6. Основные свойства сравнений

1. (рефлексивность)
a a(mod m) для любого a Z
2. (симметричность)
Если a b(mod m) ,то b a(mod m)
3. (транзитивность)
Если b a(mod m) и b c(mod m) , то a c(mod m)
• Свойства 1, 2, 3 следуют из того, что сравнимые
числа имеют одинаковые остатки при делении на m
• Из свойств 1–3 вытекает, что отношение
сравнимости на множестве целых чисел является
отношением эквивалентности

7. Основные свойства сравнений

4. Если a b(mod m), d Z , то a d b d (mod m)
Доказательство
Если a b(mod m),то (a b) m и (a d (b d )) m
Следовательно, a d b d (mod m)
5. Любое слагаемое сравнения можно переносить
в другую часть с противоположным знаком
Доказательство
Пусть a b c(mod m)
Прибавим к обеим частям сравнения b
получим a c b(mod m)

8. Основные свойства сравнений

6. Обе части сравнения можно умножать на одно и то
же целое число, т.е.если a b(mod m) ,то ac bc(mod m)
Доказательство
Если a b(mod m) , то (a b) m и
для любого c Z c(a b) m , или (ac bc ) m
Следовательно ac bc(mod m)
7. Сравнения по одному и тому же модулю можно
почленно складывать
Доказательство
a b(mod m) a c b c(mod m)
c d (mod m) b c b d (mod m) (свойство 4)
По 3 свойству: a c b d (mod m)

9. Основные свойства сравнений

8. Сравнения по одному и тому же модулю можно
почленно перемножать
Доказательство
a b(mod m) ac bc(mod m)
(свойство 6)
c d (mod m) bc bd (mod m)
ac bd (mod m)
Тогда по 3 свойству:
9. Обе части сравнения можно возводить в одну и ту
же степень с натуральным показателем (следует
из свойства 8)
n
f
(
x
)
c
c
x
...
c
x
10. Если a b(mod m) и
–
0
1
n
произвольный многочлен с целыми коэффициентами,
то f (a) f (b) (mod m) (это свойство является
следствием свойств 9, 6, 7)

10. Основные свойства сравнений

11. Обе части сравнения и модуль можно умножить
на одно и то же натуральное число
a b(mod m), c N ac bc(mod mc)
Доказательство
Если a b(mod m),то (a b) m; a b mt ; ac bc mct
Cледовательно, (ac bc ) mc и ac bc (mod mc )
12. Обе части сравнения и модуль можно разделить
на их общий натуральный делитель
ak bk (mod mk ) a b(mod m)
Доказательство
Если ak bk(mod mk ), то ak bk mkt, t Z , или k (a b) mkt
a b mt (a b) m a b(mod m)

11. Основные свойства сравнений

13. Обе части сравнения можно разделить на их
общий множитель, если он взаимно прост с
модулем
Доказательство
ak bk (mod m), следовательно k (a b) m
Если (k , m) 1, то (a b) m (по свойству взаимно
простых чисел), т.е. a b(mod m)
14. Сравнимые по модулю m числа имеют один и тот
же наибольший общий делитель с числом m, т.е.
если a b(mod m) , то (a, m) (b, m)
Доказательство
Т. к.a b(mod m), то для некоторого t Z , a mt b
По лемме к алгоритму Евклида (a, m) (b, m)

12. Основные свойства сравнений

15. Можно добавлять (или отбрасывать) к любой части
сравнения слагаемые, кратные модулю
Пусть a b(mod m)
Т.к. mt 0(mod m), где t Z , то a mt b(mod m) (свойство 7)
16. a b(mod mk ) a b(mod m)
Если a b(mod mk) , то a b делится на mk,
а значит и на m, следовательно, a b(mod m)
17. Если a b(mod m1 ), a b(mod m2 ), ... , a b(mod mn ) , то
a b(mod m) , где m [m1 , m2 , ... , mn ]
Доказательство
Так как (a b) m1 , (a b) m2 , ... , (a b) mn , то (a b) –
общее кратное чисел m1 , m2 , ... , mn и оно делится на НОК