Конспект урока
Конспект урока
Алгебра
7 класс
Урок № 50
Линейные диофантовы уравнения
Перечень рассматриваемых вопросов:
- Диофантово уравнение.
- Разрешимость диофантова уравнения.
- Решение задач с помощью диофантова уравнения.
Тезаурус:
Диофантовым уравнением называется уравнение вида ах + bу = с (а ≠ 0, b ≠ 0), где а, b, с, х и у – целые числа.
Если c делится на НОД(а; b), то уравнение ах + bу = с имеет решение в целых числах. Если c не делится на НОД (а; b), то уравнение ах + bу = с не имеет решений в целых числах.
Основная литература:
1. Никольский С. М. Алгебра: 7 класс. // Никольский С. М., Потапов М. К., Решетников Н. Н., Шевкин А. В. – М.: Просвещение, 2017. – 287 с.
Дополнительная литература:
1. Чулков П. В. Алгебра: тематические тесты 7 класс. // Чулков П. В. – М.: Просвещение, 2014 – 95 с.
2. Потапов М. К. Алгебра: дидактические материалы 7 класс. // Потапов М. К., Шевкин А. В. – М.: Просвещение, 2017. – 96 с.
3. Потапов М. К. Рабочая тетрадь по алгебре 7 класс: к учебнику С. М. Никольского и др. «Алгебра: 7 класс». 1, 2 ч. // Потапов М. К., Шевкин А. В. – М.: Просвещение, 2017. – 160 с.
Теоретический материал для самостоятельного изучения.
Определение диофантова уравнения.
Пусть дано уравнение ах + bу = с (а ≠ 0, b ≠ 0), где а, b, с – целые числа. Если поставлена задача найти только такие его решения (х0; у0), где х0, у0 – целые числа, то это уравнение называют линейным диофантовым уравнением.
Историческая справка.
Диофантовы уравнения связаны с именем древнегреческого математика Диофанта Александрийского. О подробностях жизни Диофанта Александрийского практически ничего не известно. С одной стороны, Диофант цитирует Гипсикла (II век до нашей эры); с другой стороны, о Диофанте пишет Теон Александрийский (около 350 года нашей эры). Откуда можно сделать вывод, что жил он приблизительно в III веке нашей эры.
Решение диофантовых уравнений.
Решим линейное диофантово уравнение
2х + 3у = 6.
Выразим у через х:
Из этого равенства видно, что у будет целым только тогда, когда целое число х делится на 3, т.е. х = 3х1, где х1 – некоторое целое число. Тогда у = 2 -2х1.
Таким образом, решениями уравнения являются все пары чисел (3х1;2 -2х1).
Приведём некоторые частные решения этого уравнения.
Если х1 = 0, то х = 3х1 = 0, а у = 2 — 2 х1 = 2; решением уравнения является пара (0;2).
Если х1 = 1, то х = 3х1 = 3, а у = 2 — 2 х1 = 0;
решением уравнения является пара (3; 0)
Аналогично можно найти и другие частные решения, их бесконечно много.
Запишем ответ: пары чисел (3х1;2 -2х1).
Решение задач при помощи линейных диофантовых уравнений.
Линейные диофантовы уравнения возникают при решении некоторых задач.
Рассмотрим задачу.
У покупателя и продавца имеются монеты только по 2р. и 5р. Сможет ли покупатель заплатить за покупку стоимостью 1р.?
Если покупатель даст х монет по 2р. и у монет по 5 р., то он заплатит (2х + 5у) р. А по условию задачи это 1р. Составим уравнение:
2х + 5у = 1.
Выразим х через у из уравнения:
Из равенства видно, что х будет целым только тогда, когда у будет нечетным числом: у = 2m + 1, где m – целое число.
Тогда х = -5m – 2.
Таким образом, решением уравнения являются все пары чисел (-5m – 2; 2m + 1), где m – любое целое число.
Таким образом, способов оплаты товара стоимостью 1р. Бесконечно много. Если х окажется отрицательным, то это означает, что покупатель должен получить сдачу: х монет по 2р.
Например, пара (-2; 1) является решением уравнения. Это означает, что покупатель далодну монету по 5 р. и получил сдачу 2 монеты по 2р.
Ответ: сможет.
Разрешимость диофантова уравнения.
Не каждое диофантово уравнение имеет решение в целых числах.
Рассмотрим на примере уравнения
3х + 6у = 2 алгоритм, с помощью которого можно определить, имеет оно решение в целых числах.
1 шаг. Надо найти наибольший общий делитель чисел 3 и 6. НОД(3; 6) = 3.
2 шаг. Определить, делится ли 2 на НОД(3; 6).
3 шаг. Если 2 делится на НОД(3; 6), то уравнение имеет решение в целых числах.
Если 2 не делится на НОД (3; 6), то уравнение не имеет решений в целых числах.
Расширенный алгоритм Евклида для решения диофантовых уравнений.
Для нахождения наибольшего общего делителя двух целых неотрицательных чисел используют алгоритм Евклида. Рассмотрим его реализацию на примере чисел 24 и 17.
Разделим большее из этих чисел на меньшее, то есть 24 на 17.
Получаем 24 : 17 = 1 (ост. 7), что можно записать в виде равенства:
24 = 17 · 1 + 7.
Теперь разделим делитель на остаток, то есть 17 на 7, получим:
17 = 7 · 2 + 3.
Снова разделим делитель на остаток:
7 = 3 · 2 + 1.
Выполним деление еще раз:
3 = 1 · 3 + 0.
Мы получили остаток, равный нулю, так как 3 делится на 1 без остатка.
В представленной последовательности действий мы получали остатки: 7, 3, 1, 0. Последний остаток, не считая 0, является наибольшим общим делителем чисел 24 и 17. То есть, НОД(24; 17) = 1.
Рассмотрим еще один пример: НОД(612; 342)?
612 = 342 ∙ 1 + 270,
342 = 270 ∙ 1 + 72,
270 = 72 ∙ 3 + 54,
72 = 54 ∙ 1 + 18,
54 = 18 ∙ 3 + 0.
НОД(612; 342) = 18.
Теперь выполним действия «в обратном направлении», то есть выразим 18 (остаток) через числа 612 и 342.
Для этого в каждой строчке последовательности Евклида выразим остатки через делимое и делитель (второй столбик таблицы):
612 = 342 ∙ 1 + 270 342 = 270 ∙ 1 + 72 270 = 72 ∙ 3 + 54 72 = 54 ∙ 1 + 18 54 = 18 ∙ 3 + 0 | 270 = 612 – 342 ∙ 1 72 = 342 – 270 ∙ 1 54 = 270 – 72 ∙ 3 18 = 72 – 54 ∙ 1 |
Получаем, 18 = 72 – 54 ∙ 1 = 72 – (270 – 72 ∙ 3) = 342 – 270 ∙ 1 – (270 – (342 — 270 ∙ 1) ∙3) =
342 – ((612 – 342 ∙1) ∙ 1) – (612 – 342 ∙ 1 – (342 – (612 – 342 ∙ 1)) ∙3) = 342 – 612 + 342 – 612 + 342 + 342 ∙ 3 – 612 ∙ 3 + 342 ∙ 3 = 342 ∙ 9 – 612 ∙ 5 = 342 ∙ 9 + 612 ∙ (-5).
То есть 18 = 9 ∙ 342 + (-5) ∙ 612.
Умение выполнять действия алгоритма «в обратном направлении» понадобится нам в решении диофантовых уравнений при помощи расширенного алгоритма Евклида.
Пример: решите уравнение 24x−17y=2.
Решение.
Найдем при помощи алгоритма Евклида НОД(24, 17):
24 = 17 · 1 + 7.
17 = 7 · 2 + 3.
7 = 3 · 2 + 1.
3 = 1 · 3 + 0.
НОД (24, 17) = 1.
Выполним действия «в обратном направлении»:
1 = 7 – 3 · 2 = 7 − (17 – 7 · 2) · 2 = 7 – 17 · 2 + 7 · 4 + 5 · 7 – 2 · 17 = 5 · (24 – 17 · 1) – 2 · 17 = 5 · 24 – 5 · 17 – 2 · 17 = 5 · 24 – 7 · 17 = 24 · 5 – 17 · 7.
24 · 5 – 17 · 7 = 1; В исходном уравнении в правой части стоит число 2. Поэтому умножим обе части уравнения на 2. Получим:
24 · 10 – 17 · 14 = 2.
То есть, x0 = 10, y0 = 14 – частные решения уравнения 24x −17y = 2.Если уравнение имеет одно решение в целых числах, то оно имеет бесконечное множество других решений.
Прибавим коэффициент b к значению х.
10 + (-17) = -7.
Чтобы значение исходного уравнения не изменилось, при прибавлении одного числа к х нужно вычесть другое число изу:
14 – 24 = -10.
(-7; -10) – еще одно решение уравнения.
Значения x будут равны сумме исходного решения (х0) и любого кратного коэффициента b. То есть х = 10 + (-17t), где t – целое число.
А значение у – равны разности у0 и любого кратного коэффициента а. То есть у = 14 – 24t.
Ответ: (10 − 17t, 14 − 24t), t ∈ Z.
Разбор заданий тренировочного модуля.
1. Решите задачу:
Некий чиновник купил ослов и быков за 1770 талеров. За каждого осла он уплатил по 31 талеру, а за каждого быка – по 21 талеру. Сколько ослов и быков купил чиновник?
Пусть чиновник купил х ослов и у быков. Тогда 31х + 21у = 1770.
По смыслу задачи х и у – натуральные числа. Так как 21 и 1770 делятся на 3, то 31х делится на 3, т. е. х делится на 3: х = 3n, где n – натуральное число. Тогда 31n + 7у = 590. Откуда n =
Очевидно, что n будет целым, если 7у – 1 делится на 31.
Наименьшее натуральное у, при котором это произойдет, равно 9. При этом n = 17, х = 51. Первое решение найдено: (51; 9).
Заметим, что следующие целые n будут получаться в результате увеличения у = 9 на число, кратное 31.
При у = 9 + 21 = 40 имеем n = 10, х = 30.
При у = 40 + 9 имеем n = 3, х = 9.
При следующих значениях у значения n отрицательны. Таким образом, исходное уравнение имеет 3 решения: (51, 9), (30, 40), (9, 71).
Ответ: (51, 9), (30, 40), (9, 71).
2. Решение уравнения.
Разделите уравнения на 2 группы: уравнение имеет решение в целых числах, уравнение не имеет решений в целых числах.
7х – 5у = 2
3х + 5у = 10
2х + 4у = -1
3х – 9у = 10
6х + 9у = 2
2х – 5у = 15
1) НОД(7; 5) = 1, 2 делится на 1, следовательно, 7х – 5у = 2 имеет решение в целых числах.
2) НОД(3; 5) = 1, 10 делится на 1, следовательно, 3х + 5у = 10 имеет решение в целых числах.
3) НОД(2; 4) = 2, -1 не делится на 2, следовательно, 2х + 4у = -1 не имеет решений в целых числах.
4) НОД(3; 9) = 3, 10 не делится на 3, следовательно, 3х – 9у = 10 не имеет решений в целых числах.
5) НОД(6; 9) = 3, 2 не делится на 3, следовательно, 6х + 9у = 2 не имеет решений в целых числах.
6) НОД(2; 5) = 1, 15 делится на 1, следовательно, 2х – 5у = 15 имеет решение в целых числах.