Урок 8. Сравнения

Конспект урока

Алгебра и начала математического анализа, 10 класс

Урок №8. Сравнения.

Перечень вопросов, рассматриваемых в теме

1. понятие сравнения двух чисел;
2. понятие сравнения по модулю;
3. основные свойства сравнений.

Глоссарий по теме

Определение. Если а и b — два целых числа и их разность а — b делится на натуральное число m, то говорят, что a и b сравнимы по модулю m.

Свойства сравнений:

1. a ≡ b (mod m), b ≡ c (mod m), a ≡ c (mod m)
2. a ≡ b (mod m) b ≡ a (mod m)
3. a1 ≡ b1 (mod m), a2 ≡ b2 (mod m), … , ak ≡ bk (mod m) a1+…+ak ≡ b1+…bk(mod m)
4. a+b ≡ c (mod m) a ≡ c–b (mod m)
5. a ≡ b (mod m) a+mt ≡ b+mk(mod m) (t, k ∈ Z)
6. a ≡ b (mod m), c ≡ d (mod m) ac ≡ bd (mod m)
7. a ≡ b (mod m) ak ≡ bk(mod m)
8. a ≡ b (mod m) ak ≡ bk(mod m)
9. Если a ≡ b (mod m), (a, b) = c, (c, m) = 1 (mod m)
10. a ≡ b (mod m) ak ≡ bk (mod mk)
11. a ≡ b (mod m), a = a1d, b = b1d, m = m1d a1 ≡ b1(mod m1)
12. a ≡ b (mod m1), a ≡ b(mod m2), …, a ≡ b(mod mk) a ≡ b (mod НОК(m1,…,mk))
13. a ≡ b (mod m), d/m a ≡ b(mod d)
14. d/a, d/m, a ≡ b(mod m) d/b
15. a ≡ b (mod m) (a, m) = (b, m)

Теорема обратимости: обратный элемент для числа существует тогда и только тогда, когда это число взаимно простое с модулем.

Теорема 1. Если , то сравнение (7) имеет единственное решение.

Теорема 2. Если и число b не делится на d , то сравнение ax ≡ b (mod m) не имеет решений.

Теорема 3. Если и , b ≡ d то сравнение (7) имеет d решений.

Основная литература:

Колягин Ю.М., Ткачева М.В, Федорова Н.Е. и др., под ред. Жижченко А.Б. Алгебра и начала математического анализа (базовый и профильный уровни) 10 кл. – М.: Просвещение, 2014.

Дополнительная литература:

Шабунин М.И., Ткачева М.В., Федорова Н.Е. Дидактические материалы Алгебра и начала математического анализа (базовый и профильный уровни) 10 кл. – М.: Просвещение, 2017.

Теоретический материал для самостоятельного изучения

Два целых числа, разность которых кратна данному натуральному числу m, называются сравнимыми по модулю m. (Слово «модуль» происходит от латинского modulus, что по-русски означает «мера», «величина».) Утверждение «a сравнимо с b по модулю m» обычно записывают в виде a ≡ b (mod m), и называют сравнением. Вот примеры сравнений: 5 ≡ 1 (mod 2), 48 ≡ 0 (mod 6), 16 ≡ 9 (mod 5). Сравнение по модулю 1 выполняется для любых двух целых чисел, так как всякое число кратно 1. Два числа сравнимы по модулю 2, если они одной четности, т.е. либо оба четны, либо оба нечетны.

Определение сравнения было сформулировано в книге К. Ф. Гаусса «Арифметические исследования». Эту работу, написанную на латинском языке, начали печатать в 1797 г., но книга вышла в свет лишь в 1801 г. из-за того, что процесс книгопечатания в то время был чрезвычайно трудоемким и длительным. Первый раздел книги Гаусса так и называется: «О сравнении чисел вообще».

Сравнениями очень удобно пользоваться в тех случаях, когда достаточно знать в каких-либо исследованиях числа с точностью до кратных некоторого числа. Например, если нас интересует, на какую цифру оканчивается куб целого числа a, то нам достаточно знать a лишь с точностью до кратных числа 10, и можно пользоваться сравнениями по модулю 10.

Определение сравнений.

Определение. Если а и b — два целых числа и их разность а — b делится на натуральное число m, то говорят, что a и b сравнимы по модулю m.

Мы выражаем это записью

a ≡ b (mod m), (1)

которая читается так: а сравнимо с b по модулю m.

Делитель m мы предполагаем натуральным; он называется модулем сравнения. Наше высказывание (1) означает, что

a — b = mk, где k — целое число. (2)

Пример 1.

1) 23 ≡ 8 (mod 5), так как 23 — 8 = 15 = 5 ∙ 3;

2) 47 ≡ 11 (mod 9), так как 47–11 = 36 = 9 ∙ 4;

3) —11 ≡ 5 (mod 8), так как — 11 — 5 = —16 = 8 ∙ (-2);

4) 81 ≡ 0 (mod 27), так как 81 — 0 = 81 = 27 ∙ 3.

Последний пример показывает, что вообще, вместо того, чтобы говорить: число а делится на число m, мы можем записать a ≡ 0 (mod m), так как это означает, что а — 0 = а = mk, где k — некоторое целое число.

Например, вместо того, чтобы сказать, что а — четное число, мы можем записать a ≡ 0 (mod 2).

Таким же образом видно, что нечетное число является числом, удовлетворяющим сравнению а ≡ 1 (mod 2).

Обобщим свойства сравнений:

1. a ≡ b (mod m), b ≡ c (mod m), a ≡ c (mod m)
2. a ≡ b (mod m) b ≡ a (mod m)
3. a1 ≡ b1 (mod m), a2 ≡ b2 (mod m), … , ak ≡ bk (mod m) => a1+…+ak ≡ b1+…bk(mod m)
4. a+b ≡ c (mod m) a ≡ c–b (mod m)
5. a ≡ b (mod m) a+mt ≡ b+mk(mod m) (t, k ∈ Z)
6. a ≡ b (mod m), c ≡ d (mod m) ac ≡ bd (mod m)
7. a ≡ b (mod m) ak ≡ bk(mod m)
8. a ≡ b (mod m) ak ≡ bk(mod m)
9. Если a ≡ b (mod m), (a, b) = c, (c, m) = 1 (mod m)
10. a ≡ b (mod m) ak ≡ bk (mod mk)
11. a ≡ b (mod m), a = a1d, b = b1d, m = m1d a1 ≡ b1(mod m1)
12. a ≡ b (mod m1), a ≡ b(mod m2), …, a ≡ b(mod mk) a ≡ b (mod НОК(m1,…,mk))
13. a ≡ b (mod m), d/m a ≡ b(mod d)
14. d/a, d/m, a ≡ b(mod m) d/b
15. a ≡ b (mod m) (a, m) = (b, m)

Нахождение обратного элемента

Задача нахождения обратного элемента: найти b=a-1 (mod n), где a и n заданы, b неизвестно.

Элемент b называется обратным к a по модулю n, если a∙b≡1(mod n). Тогда пишут, что b ≡ a–1 (mod n). Справедлива

Теорема обратимости:

Существует a-1 (mod n) (a, n) = 1.

То есть, обратный элемент для числа существует тогда и только тогда, когда это число взаимно простое с модулем.

Найти обратный элемент можно с помощью расширенного алгоритма Евклида:

Пусть a > n; a, Расширенный алгоритм Евклида находит числа x, y: ax+ny = НОД(a, n).

Вычисляет цепочка равенств:

a = nq1 + r1;

n = r1q2 + r2;

r1 = r2q3 + r3;

…..

rk−2 = rk-1qk + rk;

rk−1 = rkqk+1.

Используя эту цепочку, восстанавливаем:

rk = rk-2 – rk-1qk= rk-2 – (rk-3 – rk-2qk-1)qk = … =ax+ny.

Получаем сравнение ax+ny≡1(mod n). Поскольку ny≡0(mod n), то ax≡1(mod n), а значит полученное с помощью расширенного алгоритма Евклида число x как раз и есть искомый обратный элемент к числу a по модулю n.

Пример 2.

Вычислить элемент, обратный а по mod n, если a=9; n=29;

Решение:

Воспользуемся расширенным алгоритмом Евклида:

29=9∙3+2

9=2∙4+1

2=1∙2+0

Обратный ход:

1=9-2∙4=9∙1-(29-9∙3)∙4=9∙13-29∙4.

Проверка:

13∙9=117. 117≡1(mod( 29)).

Ответ: обратный элемент = 13.

Сравнения первой степени

Сравнения первой степени имеют вид

a1x+a0≡0 (mod m) (6).

Перенеся свободный член в правую часть сравнения, и меняя обозначения коэффициентов, получим

ax≡ b (mod m) (7)

При решении таких сравнений рассматривают два случая:

и .

Теорема 1. Если , то сравнение (7) имеет единственное решение.

Теорема 2. Если и число b не делится на d, то сравнение ax≡ b (mod m) не имеет решений.

Теорема 3. Если и b ≡ d, то сравнение (7) имеет d решений.

Решение сравнений первой степени

Рассмотрим 2 способа решения сравнений первой степени, в основе которых лежит приведение сравнения первой степени к равносильному сравнению с коэффициентом при x , равному единице.

Проиллюстрируем решение сравнения этими способами на следующем примере:

Решить сравнение 25х≡15(mod 17)

Разбор решения заданий тренировочного модуля

№1. Тип задания: выбор элемента из выпадающего списка

Решите сравнение 21х≡13 (mod 7)

Выпадающий список:

1. 4
2. 2
3. 5
4. 6

Решим данное сравнение:

Наибольший общий делитель 

a=25 и m=7:

d=NOD(25,7)=1

Так как  b:d=10:1=10 целое, то, следовательно, сравнение имеет  d=1 решений по модулю  m= 7.

Числа, удовлетворяющие сравнению: 

x=7t+6 (t∈Z).

Решение сравнения: 

x≡6(mod7).

Верный ответ 4. 6

№2. Тип задания: ввод с клавиатуры пропущенных элементов в тексте.

Вычислить элемент, обратный а по mod n, если a=7; n=17

Обратный элемент_____

Решим данное задание:

Воспользуемся расширенным алгоритмом Евклида:

17=7∙2+1

7=2∙3+1

2=1∙2+0

Обратный ход:

1=7-2∙3=7∙1-(17-7∙2)∙2=7∙5-17∙2.

Проверка:

5∙7=35. 35≡1(mod( 17)).

Ответ:

Обратный элемент 5.