Лекция 5. Тема Теория сравнений 15. Сравнения в кольце целых чисел и их свойства 15 Сравнения по фиксированному модулю

• Название: Тема Теория сравнений 15. Сравнения в кольце целых чисел и их свойства 15 Сравнения по фиксированному модулю
• Дата: 22.10.2022
• Размер: 28.13 Kb.
• Имя файла: Лекция 5.docx
• Тип: Документы; #748422

Тема 2. Теория сравнений

§ 15. Сравнения в кольце целых чисел и их свойства

15.1. Сравнения по фиксированному модулю

Опр.1 Целые числа а и b сравнимы между собой по модулю (натуральному числу) m (m > 1) и пишут , если при делении этих чисел на m получают одинаковые остатки.

Пример. , т.к. 15 = 6 2 + 3; 27 = 6 4 + 3.

Теорема1. Если целые числа а и b сравнимы по модулю m, то (а – b) m.

Доказательство: т.к. , то по опр.1 а = mq₁ + r, b = mq₂ + r.

а – b = m(q₁ – q₂) (a – b) m.

Опр.2 Целые числа а и b сравнимы по модулю m (m > 1), если (а – b) m.

Теорема2. Отношение сравнимости на множестве целых чисел Z является отношением эквивалентности.

Доказательство: покажем, что отношение сравнимости по данному модулю m обладает рефлексивностью, т.е. .

а – а = 0, а 0 делится на любое число, значит 0 m, т.е. .

Покажем, что отношение сравнимости по данному модулю m обладает симметричностью, т.е. . Это очевидно.

Покажем, что отношение сравнимости по данному модулю m обладает транзитивностью, т.е. .

а – с = ((а – b) + (b – c)) m, (а- b) m, и (b – c) m, значит и (а – с) m, т.е. . Теорема доказана.

Свойства

1⁰. Обе части сравнения можно умножать на любое целое число n.

Доказательство: покажем, что

.

= n(a – b) m т.к. (а- b) m.

2⁰. К обеим частям сравнения можно прибавлять любое целое число.

Доказательство: покажем, что

.

(а + n) – (b + n) = (a + b) m. По опр.2 .

3⁰. Сравнения по одному модулю можно складывать и вычитать.

Доказательство: покажем, что

.

(а ± c) – (b ± d) = (a - b) m, т.к. (а- b) m (с – d) .

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

Доказательство: покажем, что

.

(а c) – (bd) = (aс - bс) m, т.к.

(а- b) m (с – d) .

5⁰. Из одной части сравнения слагаемые можно переносить в другую часть с противоположным знаком.

Доказательство: покажем, что

.

, - рефлексивность. По свойству 3⁰ или а .

6⁰. К любой части сравнения можно прибавить произвольное целое число, кратное модулю, т.е. .

Доказательство: = ((a – b) + km) mт.к. (а- b) m km m.

7⁰. Сравнения можно возводить в любую натуральную степень: , .

Доказательство: методом математической индукции.

1. n = 1 - по условию.

2. n = k. Пусть верно .

3. Покажем, что формула верна для n = k + 1.

Имеем ; . По свойству 4 эти сравнения можно перемножить, получим - что и требовалось доказать.

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

Доказательство: покажем, что , таких, что а d и b d, и (m, d) = 1, из условия .

Т.к. а d и b d, то а = а₁d и b = b₁d. Разность а – b = а₁d - b₁d = (а₁ - b₁ )d. Т.к. (а₁ - b₁)d и (d, m) = 1, то (а₁ - b₁) , значит а₁ b₁ (modm).

a₁ = , b₁ = и значит .

9⁰. Если в выражении f(a₁, a₂, …,a_k) = … , где А,a₁, a₂, …,a_k Z; m₁, m₂, …,m_k–неотрицательные целые числа, заменить А,a₁, a₂, …,a_k на сравнимые с ними по модулю m соответствующие числа B,b₁, b₂, …,b_k, то g(b₁, b₂, …,b_k) сравнимо с f(a₁, a₂, …,a_k) по модулю m.

Доказательство: по условию

, , …, . Эти сравнения соответственно возведем в степени m₁, m₂, …,m_k. Получим

, , …, .

По условию , перемножая эти сравнения, получим

. Суммируя сравнения такого вида, получим … … .

И f(a₁, a₂, …,a_k) g(b₁, b₂, …,b_k) .

Следствие. Если в многочлене с целыми коэффициентами

f(x) = a_nxⁿ + a_n-1x^n-1 + …+a₁x + a₀, определенном на множестве целых чисел Z, заменить коэффициенты a_n, a_n-1, …a₁, a₀ коэффициентами b_n, b_n-1, …b₁, b₀, сравнимыми по модулю m соответственно, то многочлен g(x) = b_nxⁿ + b_n-1x^n-1 + …+b₁x + b₀сравним с данным многочленом f(x) при любом целом х.

Доказательство: пусть и запишем очевидное:

, х . , к = . Суммируя эти сравнения по к от n до 0: или f(х) g(х) .

15.2. Свойства сравнений

1⁰. Все части сравнения можно умножать на любое натуральное число.

Доказательство: (а – b) m (по условию). Значит а – b = кm. Это равенство умножим на натуральное число n: аn – bn = (кm)n .

2⁰. Обе части сравнения и модуль можно разделить на их общий делительd.

Доказательство: пусть а , b , m , тогда а = da₁, b = db₁, m = dm₁. Из условия следует, что а – b = mt. Подставляя, получим: da₁ - db₁ = (dm₁)t - d(m₁t), тогда a₁ - b₁ = m₁t или . , , , и значит .

3⁰. Если по некоторым модулям m₁, m₂, …, m_k, то по их наименьшему общему кратному: (mod [m₁, m₂, …, m_k]).

Доказательство: т.к. : (modm₁), (modm₂),…, (modm_к), то (а - b) делится на m₁, m₂, …, m_k, следовательно (а – b) для модулей m₁, m₂, …, m_k является общим кратным. Поэтому (а – b) [m₁, m₂, …, m_k], следовательно (mod [m₁, m₂, …, m_k]).

4⁰. Если (modm) m d, то (modd).

Доказательство: (а – b) m, m d следовательно (а – b) d (транзитивность), значит (modd).

5⁰. Если одна часть сравнения (modm) и модуль делятся на число d, то и вторая часть сравнения делится на это число d.

Доказательство: пусть а d и m d. Докажем, что и b d.

(а – b) m а – b = mt, b = a – mt.

Т.к. а d и m d, то (а – mt) d b d.

6⁰. Если (modm), то (а, m) = (b, m).

Доказательство: обозначим D_a,m – множество общих делителей чисел а и m, D_b,m – множество общих делителей чисел b и m. Пусть d D_a,m –произвольный делитель чисел а и m. Тогда из условия (modm) найдем, что b = а – mt b d d D_b,m D_a,m D_b,m (1).

С другой стороны, пусть к D_b,m –произвольный делитель чисел b и m и является делителем чисел а и m ,т.к. а = b + mt D_b,m D_а,m (2).

Из (1) и (2) следует, что D_b,m D_а,m , значит (а, m) = (b, m).

§ 16. Вывод признаков делимости

Одним из методов нахождения делителя, основанных на сравнении, является метод Паскаля.

Пусть некоторое натуральное число а, записанное в системе счисления с основанием q, имеет вид: а = а_nqⁿ + a_n-1q^n-1 + …+ a₁q + a₀, где 0 а_n,a_n-1, … a₁, a₀ < q, а_n ≥ 1. И пусть число b = а_nrⁿ + a_n-1r^n-1 + …+ a₁r + a₀. Тогда из условия (modm) следует, что если b m , то и a m. Если b не делится на m, то и а не делится на m. Это и есть признак Паскаля.

Пример. Рассмотрим числа 3, 9. Запись в десятичной системе счисления:

а = а_n10ⁿ + a_n-110^n-1 + …+ a₁10 + a₀. При делении 10^к на 3 и на 9 в остатке получается 1, т.е. r₀ = r₁ = …= r_n = 1 и тогда b = а_n1 + a_n-11+ …+ a₁1 + a₀ = а_n + a_n-1+ …+ a₁ + a₀ .

Вывод: натуральное число а делится на 3 (на 9) тогда и только тогда, когда на 3 (на 9) делится сумма цифр этого числа, записанного в десятичной системе счисления.

Выведем признак делимости на 11. Заметим, что четная степень 10^2к при делении на 11 в остатке дает 1, а при делении нечетной степени числа 10^{2к – 1} на 11 в остатке дает -1. Тогда b = a₀ + a₁(-1) + а₂ + а₃ (-1)+ а₄ + … = (a₀ + а₂ + а₄ + …) – (a₁ + а₃ + а₅ + …). Итак, натуральное число делится на 11 тогда и только тогда, когда разность между суммой цифр, стоящих на четных местах и суммой цифр, стоящих на нечетных местах, делится на 11.

Пример. Делится ли на 11 число 53746?

Решение: 6 + 7 + 5 – (3 + 4) = 18 – 7 = 11 – делится на 11, значит и 53746 тоже делится на 11.