Задача 1. Допустим, в аквариуме живут осьминоги и морские звёзды. У осьминогов по 8 ног, а у морских звёзд – по 5. Всего конечностей насчитывается 39. Сколько в аквариуме животных?
Решение. Пусть х — количество морских звёзд, у – количество осьминогов. Тогда у всех осьминогов по 8у ног, а у всех звёзд 5х ног. Составим уравнение: 5х + 8у = 39.
Заметим, что количество животных не может выражаться нецелым или отрицательным числами. Следовательно, если х – целое неотрицательное число, то и у=(39 – 5х)/8 должно быть целым и неотрицательным, а, значит, нужно, чтобы выражение 39 – 5х без остатка делилось на 8. Простой перебор вариантов показывает, что это возможно только при х = 3, тогда у = 3. Ответ: (3; 3).
Уравнения, вида ах+bу=с, называются диофантовыми, по имени древнегреческого математика Диофанта Александрийского. Жил Диофант, по-видимому, в 3 в. н. э., остальные известные нам факты его биографии исчерпываются таким стихотворением-загадкой, по преданию выгравированным на его надгробии:
Прах Диофанта гробница покоит; дивись ей и камень
Мудрым искусством его скажет усопшего век.
Волей богов шестую часть жизни он прожил ребенком.
И половину шестой встретил с пушком на щеках.
Только минула седьмая, с подругой он обручился.
С нею, пять лет, проведя, сына дождался мудрец;
Только полжизни отцовской возлюбленный сын его прожил.
Отнят он был у отца ранней могилой своей.
Дважды два года родитель оплакивал тяжкое горе,
Тут и увидел предел жизни печальной своей.
Сколько же лет прожил Диофант Александрийский?
Задача 2. На складе имеются гвозди в ящиках по 16,17 и 40 кг. Может ли кладовщик выдать 100 кг гвоздей, не вскрывая ящики? (метод прямого перебора)
Разберем метод решения относительно одного неизвестного.
Задача 3. В каталоге картинной галереи всего 96 картин. На каких-то страницах расположено 4 картины, а на каких-то 6. Сколько страниц каждого вида есть в каталоге?
Решение. Пусть х – количество страниц с четырьмя картинами,
у – количество страниц с шестью картинами,
тогда по условию этой задачи можно составить уравнение:
Решаем это уравнение относительно того из неизвестных, при котором наименьший (по модулю) коэффициент. В нашем случае это 4х, то есть:
Делим все уравнение на этот коэффициент:
Остатки при делении на 4: 1,2,3. Подставим вместо у эти числа.
Если у=1, то х=(96-6∙1):4=90:4 — Не походит, решение не в целых числах.
Если у=2, то х=(96-6∙2):4=21 – Подходит.
Если у=3, то х=(96-6∙3):4=78:4 — Не походит, решение не в целых числах.
Итак, частным решением является пара (21;2), а это значит, что на 21 странице расположено по 4 картины, а на 2 страницах по 6 картин.
Разберем метод решения с использованием алгоритма Евклида.
Задача 4. В магазине продаётся шоколад двух видов: молочный и горький. Весь шоколад хранится в коробках. Молочного шоколада на складе имеется 7 коробок, а горького 4. Известно, что горького шоколада было на одну плитку больше. Сколько плиток шоколада находятся в коробках каждого вида?
Решение. Пусть х – количество плиток молочного шоколада в одной коробке,
у – количество плиток горького шоколада в одной коробке,
тогда по условию этой задачи можно составить уравнение:
Решим это уравнение, используя алгоритм Евклида.
Выразим 7=4∙1+3, => 3=7-4∙1.
Выразим 4=3∙1+1, => 1=4-3∙1=4-(7-4∙1)=4-7+4∙1=4∙2-7∙1=1.
Итак, получается х=1; у=2.
А это значит, что молочный шоколад лежит в коробке по 1 штуке, а горький по 2 штуки.
Разберем метод поиска частного решения и общей формулы решений.
Задача 5. В африканском племени Тумбе-Юмбе два аборигена Тумба и Юмба работают парикмахерами, причем Тумба всегда заплетает своим клиентам по 7 косичек, а Юмба по 4 косички. Сколько клиентов обслужили мастера по отдельности за смену, если известно, что вместе они заплели 53 косички?
Решение. Пусть х – количество клиентов Тумбы,
у – количество клиентов Юмбы,
Теперь чтобы найти частные решения уравнения ( , ), заменим данную нам сумму чисел на 1. Это заметно упростит поиск подходящих чисел. Получим:
Решим это уравнение методом подстановки.
Остатки при делении на 4: 1, 2, 3. Подставим вместо х эти числа:
Если х=1, то у=(1-7):4 – не подходит, т.к. решение не в целых числах.
Если х=2, то у=(1-7∙2):4 – не подходит, т.к. решение не в целых числах.
Если х=3, то у=(1-7∙3):4=-5 – подходит.
Затем умножим получившиеся значения на начальное значение суммы, которую мы заменяли на 1, т.е.
Мы нашли частное решение уравнения(1). Проверим его, подставив начальное уравнение:
Ответ сошелся. Если бы, мы решали абстрактное уравнение, то можно было бы на этом остановиться. Однако мы решаем задачу, а поскольку Тумба не мог заплести отрицательное число косичек, нам необходимо продолжать решение. Теперь составим формулы для общего решения. Чтобы это сделать вычтем из начального уравнения(1) уравнение с подставленными значениями (3). Получим:
Вынесем общие множители за скобки:
Перенесем одно из слагаемых из одной части уравнения в другую:
Теперь стало видно, что чтобы уравнение решалось (х-159) должно делиться на -4, а (у+265) должно делиться на 7. Введем переменную n, которая будет отображать это наше наблюдение:
Перенесем слагаемые из одной части уравнения в другую:
Мы получили общее решение данного уравнения, теперь в него можно подставлять различные числа и получать соответствующие ответы.
Например, пусть n=39, тогда
А это значит, что Тумба заплел косички 3 клиентам, а Юмба 8 клиентам.
Решите задачи различными методами.
Задача 6: Вовочка купил ручки по 8 рублей и карандаши по 5 рублей. Причем за все карандаши он заплатил на 19 рублей больше, чем за все ручки. Сколько ручек и сколько карандашей купил Вовочка? (метод поиска общего решения, решение относительно одного не известного, использование алгоритма Евклида).
Задача 7. Куплены фломастеры по 7 рублей и карандаши по 4 рубля за штуку, всего на сумму 53 рубля. Сколько куплено фломастеров и карандашей?
Задача 8.(муниципальный тур ВОШ 2014-2015 г.) : на планете С в ходу два вида монет: по 16 тугриков и по 27 тугриков. Можно ли с их помощью купить товар, ценой в 1 тугрик?
Задача 9. Шехерезада рассказывает свои сказки великому правителю. Всего она должна рассказать 1001 сказку. Сколько ночей потребуется Шехерезаде, чтобы рассказать все свои сказки, если в какие-то ночи она будет рассказывать по 3 сказки, а в какие-то по 5? За сколько ночей Шехерезада расскажет все свои сказки, если хочет сделать это как можно быстрее? Сколько ночей понадобится Шехерезаде, если ей утомительно рассказывать по пять сказок за ночь, поэтому таких ночей должно быть как можно меньше?
Задача10. (вспомним «Водолея») Как налить 3 литра воды, имея 9-литровую и 5-литровую емкости?
Задача 11. Вовочка отлично успевает по математике. В дневнике у него только пятерки и четверки, причем пятерок больше. Сумма всех Вовочкиных оценок по математике равна 47. Сколько Вовочка получил пятерок и сколько четверок?
Задача 12. Кощей Бессмертный устроил питомник по разведению Змеев Горынычей. В последнем выводке у него есть Змеи о 17-ти головах и о 19-ти головах. Всего этот выводок насчитывает 339 голов. Сколько 17-тиголовых и сколько 19-тиголовых Змеев вывелось у Кощея?
Ответы: Диофант прожил 84 года;
задача 2: 4 ящика по 17 кг и 2 ящика по 16 кг;
задача 6: куплено 7 карандашей и 8 ручек, то есть (7,2) – частное решение и у = 2 + 5n, х = 7 + 8n, где nє Z – общее решение;
задача 7: (-53; 106) – частное решение, х=4n-53, у=-7n+106 – общие решения, при n=14, х=3, у=8, то есть куплено 3фломастера и 8 карандашей;
задача 8: например, заплатить 3 монеты по 27 тугриков и получить сдачу 5 монет по 16 тугриков;
задача 9: (2002; -1001) – частное решение, х=-5 n+2002, у=3n-1001 – общее решение, при n=350, у=49, х=252, то есть 252 ночи по 3 сказки и 49 ночей по 5 сказок — всего 301 ночь; самый быстрый вариант: 2 ночи по три сказки и 199 ночей по 5 сказок — всего 201 ночь; самый долгий вариант: 332 ночи по 3 сказки и 1 ночь 5 сказок — всего 333 ночи.
задача 10: например, 2 раза налить воду 9-тилитровой банкой и 3 раза вычерпать ее 5-тилитровой банкой;
задача 11: Вовочка получил 7 пятерок и 4 четверки;
задача 12: 11 Змеев о 17-ти головах и 8 Змеев о 19-ти головах.
Видео:Классический способ решения Диофантовых уравнений ➜ Решите уравнение в целых числах ➜ 13x-7y=6Скачать
Линейное диофантово уравнение и 4 способа его решения
Разделы: Математика
Првило 1. Если с не делится на d, то уравнение ах + ву = с не имеет решений в целых числах. Н.О.Д.(а,в) = d.
Правило 2. Чтобы найти решение уравнения ах + ву = с при взаимно-простых а и в, нужно сначала найти решение (Хо ; уо) уравнения ах + ву = 1; числа СХо , Суо составляют решение уравнения ах + ву = с.
Решить в целых числах (х,у) уравнение
Первый способ. Нахождение частного решения методом подбора и запись общего решения.
Знаем, что если Н.О.Д.(а;в) =1, т.е. а и в взаимно-простые числа, то уравнение (1)
имеет решение в целых числах х и у. Н.О.Д.(5;8) =1. Методом подбора находим частное решение: Хо = 7; уо =2.
Итак, пара чисел (7;2) — частное решение уравнения (1).
Значит, выполняется равенство: 5 x 7 – 8 x 2 = 19 … (2)
Вопрос: Как имея одно решение записать все остальные решения?
Вычтем из уравнения (1) равенство (2) и получим: 5(х -7) – 8(у — 2) =0.
Отсюда х – 7 = . Из полученного равенства видно, что число (х – 7) будет целым тогда и только тогда, когда (у – 2) делится на 5, т.е. у – 2 = 5n, где n какое-нибудь целое число. Итак, у = 2 + 5n, х = 7 + 8n, где n Z.
Тем самым все целые решения исходного уравнения можно записать в таком виде:
n Z.
Второй способ. Решение уравнения относительно одного неизвестного.
Решаем это уравнение относительно того из неизвестных, при котором наименьший (по модулю) коэффициент. 5х — 8у = 19 х = .
Остатки при делении на 5: 0,1,2,3,4. Подставим вместо у эти числа.
Если у = 0, то х = =.
Если у =1, то х = =.
Если у = 2, то х = = = 7 Z.
Если у =3, то х = =.
Если у = 4 то х = =.
Итак, частным решением является пара (7;2).
Тогда общее решение: n Z.
Третий способ. Универсальный способ поиска частного решения.
Для решения применим алгоритм Евклида. Мы знаем, что для любых двух натуральных чисел а, в, таких, что Н.О.Д.(а,в) = 1 существуют целые числа х,у такие, что ах + ву = 1.
1. Сначала решим уравнение 5m – 8n = 1 используя алгоритм Евклида.
2. Затем найдем частное решение уравнения (1)по правилу 2.
3. Запишем общее решение данного уравнения (1).
1. Найдем представление: 1 = 5m – 8n. Для этого используем алгоритм Евклида.
8 = 5 1 + 3.
5 = 3
3 = 2 .
Из этого равенства выразим 1. 1 = 3 — 2 = 3 – (5 — 3 ) =
= 3 — 5 = 3 = (8 — 5 — 5 82 -5
= 5(-2). Итак, m = -3, n = -2.
2. Частное решение уравнения (1): Хо = 19m; уо =19n.
Отсюда получим: Хо =19; уо =19 .
Пара (-57; -38)- частное решение (1).
3. Общее решение уравнения (1): n Z.
Четвертый способ. Геометрический.
1. Решим уравнение 5х – 8у = 1 геометрически.
2. Запишем частное решение уравнения (1).
3. Запишем общее решение данного уравнения (1).
Отложим на окружности последовательно друг за другом равные дуги, составляющие
-ю часть полной окружности. За 8 шагов получим все вершины правильного вписанного в окружность 8-угольника. При этом сделаем 5 полных оборотов.
На 5 – ом шаге получили вершину, соседнюю с начальной, при этом сделали 3 полных оборота и еще прошли — ю часть окружности, так что х = у + .
Итак, Хо = 5, уо =3 является частным решением уравнения 5х – 8у = 1.
2. Частное решение уравнения (1): Хо = 19 уо =19
3. Общее решение уравнения (1): n Z.
Видео:Математика. Линейные диофантовы уравнения с двумя неизвестными. Центр онлайн-обучения «Фоксфорд»Скачать
Алгебра. 7 класс
Конспект урока
Линейные диофантовы уравнения
Перечень рассматриваемых вопросов:
- Диофантово уравнение.
- Разрешимость диофантова уравнения.
- Решение задач с помощью диофантова уравнения.
Диофантовым уравнением называется уравнение вида ах + 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 веке нашей эры.
Решение диофантовых уравнений.
Решим линейное диофантово уравнение
Выразим у через х:
Из этого равенства видно, что у будет целым только тогда, когда целое число х делится на 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)
Аналогично можно найти и другие частные решения, их бесконечно много.
Решение задач при помощи линейных диофантовых уравнений.
Линейные диофантовы уравнения возникают при решении некоторых задач.
У покупателя и продавца имеются монеты только по 2р. и 5р. Сможет ли покупатель заплатить за покупку стоимостью 1р.?
Если покупатель даст х монет по 2р. и у монет по 5 р., то он заплатит (2х + 5у) р. А по условию задачи это 1р. Составим уравнение:
Выразим х через у из уравнения:
Из равенства видно, что х будет целым только тогда, когда у будет нечетным числом: у = 2m + 1, где m – целое число.
Таким образом, решением уравнения являются все пары чисел (-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), что можно записать в виде равенства:
Теперь разделим делитель на остаток, то есть 17 на 7, получим:
Снова разделим делитель на остаток:
Выполним деление еще раз:
Мы получили остаток, равный нулю, так как 3 делится на 1 без остатка.
В представленной последовательности действий мы получали остатки: 7, 3, 1, 0. Последний остаток, не считая 0, является наибольшим общим делителем чисел 24 и 17. То есть, НОД(24; 17) = 1.
Рассмотрим еще один пример: НОД(612; 342)?
612 = 342 ∙ 1 + 270,
342 = 270 ∙ 1 + 72,
Теперь выполним действия «в обратном направлении», то есть выразим 18 (остаток) через числа 612 и 342.
Для этого в каждой строчке последовательности Евклида выразим остатки через делимое и делитель (второй столбик таблицы):
612 = 342 ∙ 1 + 270
342 = 270 ∙ 1 + 72
270 = 612 – 342 ∙ 1
72 = 342 – 270 ∙ 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):
Выполним действия «в обратном направлении»:
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 к значению х.
Чтобы значение исходного уравнения не изменилось, при прибавлении одного числа к х нужно вычесть другое число изу:
(-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 группы: уравнение имеет решение в целых числах, уравнение не имеет решений в целых числах.
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 имеет решение в целых числах.
📸 Видео
Как решать Диофантовы уравнения ★ 9x+13y=-1 ★ Решите уравнение в целых числахСкачать
Диофантовы уравнения x+y=xyСкачать
Решите уравнение в целых числах: y²+1=2^x ➜ Как решать диофантовы уравненияСкачать
ПЕРЕЧНЕВЫЕ ОЛИМПИАДЫ. Диофантовы уравненияСкачать
Решение диофантовых уравненийСкачать
Линейные диофантовы уравненияСкачать
Как решать Диофантовы уравнения ➜ Решите уравнение в целых числах 4x+5y=6Скачать
Решите уравнение в целых числах 5x-4y=3 ➜ Как решать Диофантовы уравнения?Скачать
#86. Делимость и диофантовы уравнения! ТРУДНАЯ ЗАДАЧА!Скачать
Решите уравнение в целых числах ★ √x+√y=√50 ★ Как решать диофантовы уравнения?Скачать
Диофантовы уравнения x²+xy-y=2Скачать
Алексей Савватеев "Диофантовы уравнения". Лекции 1-2Скачать
Курсы повышения квалификации. Математика. Занятие 12. Диофантовы уравненияСкачать
Урок 14 Решение задач с помощью уравнений (5 класс)Скачать
Диофантовы уравнения x³-y³=91Скачать
Решите уравнение в целых числах 3x^2+5y^2=345 ✱ Диофантовы уравнения ✱ Как решать?Скачать
РЕШАЕМ ДИОФАНТОВОЕ УРАВНЕНИЕ | ПРОСТЫМИ СЛОВАМИСкачать