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

Сентябрь 16, 2022

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

Содержание

2. Числовые сравнения. Понятие сравнения Определение 1 Целые числа a и b называются сравнимыми по модулю m,
3. Теорема 1 Следующие утверждения равносильные: (1) (2) существует t ϵ Z ,что (3) a и b
4. Доказательство Докажем, что из (1) следует (2). По определению имеем: 2. Докажем, что из (2) следует
5. Определение 2 Числа a и b называются сравнимыми по модулю m, если они имеют одинаковые остатки
6. Основные свойства сравнений 1. (рефлексивность) для любого 2. (симметричность) Если ,то 3. (транзитивность) Если и ,
7. 4. Если , , то Доказательство Если ,то Следовательно, 5. Любое слагаемое сравнения можно переносить в
8. 6. Обе части сравнения можно умножать на одно и то же целое число, т.е.если ,то Доказательство
9. 8. Сравнения по одному и тому же модулю можно почленно перемножать Доказательство (свойство 6) Тогда по
10. 11. Обе части сравнения и модуль можно умножить на одно и то же натуральное число ,
11. 13. Обе части сравнения можно разделить на их общий множитель, если он взаимно прост с модулем
13. Скачать презентацию

Слайд 2

Числовые сравнения. Понятие сравнения
Определение 1
Целые числа a и b называются

сравнимыми по модулю m, если разность a - b делится на m
Обозначение:
Примеры

Слайд 3

Теорема 1 Следующие утверждения равносильные:
(1)
(2) существует t ϵ Z ,что
(3)

a и b при делении на m дают одинаковые остатки (т.е. a и b равноостаточны)

Слайд 4

Доказательство
Докажем, что из (1) следует (2).
По определению имеем:
2. Докажем,

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

Слайд 5

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

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

Слайд 6

Основные свойства сравнений
1. (рефлексивность)
для любого
2. (симметричность)
Если ,то
3. (транзитивность)
Если и ,

то
Свойства 1, 2, 3 следуют из того, что сравнимые числа имеют одинаковые остатки при делении на m
Из свойств 1–3 вытекает, что отношение сравнимости на множестве целых чисел является отношением эквивалентности

Слайд 7

4. Если , , то
Доказательство
Если ,то
Следовательно,
5. Любое слагаемое сравнения можно

переносить в другую часть с противоположным знаком
Доказательство
Пусть
Прибавим к обеим частям сравнения
получим

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

Слайд 8

6. Обе части сравнения можно умножать на одно и то же

целое число, т.е.если ,то
Доказательство
Если , то и
для любого , или
Следовательно
7. Сравнения по одному и тому же модулю можно почленно складывать
Доказательство
(свойство 4)
По 3 свойству:

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

Слайд 9

8. Сравнения по одному и тому же модулю можно почленно перемножать

Доказательство
(свойство 6)
Тогда по 3 свойству:
9. Обе части сравнения можно возводить в одну и ту же степень с натуральным показателем (следует из свойства 8)
10. Если и – произвольный многочлен с целыми коэффициентами, то (это свойство является следствием свойств 9, 6, 7)

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

Слайд 10

11. Обе части сравнения и модуль можно умножить на одно и

то же натуральное число
,
Доказательство
Если ,то
Cледовательно,
12. Обе части сравнения и модуль можно разделить на их общий натуральный делитель
Доказательство
Если

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

Слайд 11

13. Обе части сравнения можно разделить на их общий множитель, если

он взаимно прост с модулем
Доказательство
, следовательно
Если (по свойству взаимно простых чисел), т.е.
14. Сравнимые по модулю m числа имеют один и тот же наибольший общий делитель с числом m, т.е. если , то
Доказательство
Т. к. , то для некоторого ,
По лемме к алгоритму Евклида

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