Нелинейные диофантовы уравнения и способы их решения

Об одном нелинейном диофантовом уравнении

Классы: 7 , 8 , 9

Описанное ниже исследование явилось результатом совместного творчества учителя и группы ребят, увлекающихся математикой и программированием. Совместная работа над этой проблемой показала креативные возможности соединения математики и информатики.

Следует отметить, что математическую сторону исследования можно поручать одним учащимся, построение модели математического явления – другим, а можно организовать работу так, чтобы исследование осуществлялось от начала и до конца одной и той же группой учеников. Всё зависит от их интересов, возможностей, и т. д.

Мы убеждёны в плодотворности и перспективности подобных занятий, ибо именно на стыке наук рождаются открытия!

В этой работе мы будем рассматривать решение нелинейного диофантова уравнения вида axy+bx+cy=d, где a, b, c, d – целые числа, и решение отыскивается также среди целых чисел.

Если a=0, то уравнение принимает вид bx+cy=d; решение этого классического уравнения подробно описано в литературе, программа его решения на компьютере опубликована http://morozko1967.narod.ru/soft.htm.

Пусть a0. Тогда уравнение

можно записать в виде

Зададим себе вопрос: может ли ax+c быть равным нулю? Да, если c делится на a и x= –c/a. Тогда решение существует, если bx=d, иными словами, bc+ad=0. Итак, мы получили такой вывод: если bc+ad=0 и c делится на а, то существует решение:

x= –c/a, y – любое целое число.

Точно также, если b делится на а, то существует решение

x – любое число, y= –b/a. Если bc+ad=0, но ни с, ни b не делятся на а, то решений нет.

Пусть теперь bc+ad0. Тогда нет целого х, обращающего в 0 выражение (ax+c). В этом случае уравнение можно записать в виде

Докажем, что уравнение (3) имеет конечное число целочисленных решений. Рассмотрим функцию

Естественно, эта функция является биекцией. Графиком функции является гипербола.

Значит, при достаточно больших значениях переменной х значение переменной y близко к

Между какими целыми числами заключено это число?

Начиная с некоторого значения переменной х переменная y, стремясь к

и остаётся дробной. Точно также, если отрицательное х велико по модулю, то переменная y, стремясь к

и остаётся дробной. Следовательно, уравнение (3) имеет конечное число целочисленных решений, и их можно поручить отыскать компьютеру простым перебором.

Но для этого необходимо найти отрезок на оси абсцисс, вне которого гарантированно нет целочисленных решений уравнения (3).

Если b не делится на а, то, очевидно, что границы целочисленных х равны

Если b делится на а, то границы целочисленных х равны

Рассмотрим эти два случая отдельно.

Случай 1. Пусть сначала b не делится на а. Найдём

и y=B удовлетворяют уравнению (1). Поэтому

Далее нам потребуется…

Лемма. Пусть a, b – целые, отличные от нуля. Тогда

Если b не делится на а, то

Сначала докажем, что для любого нецелого х

Действительно, по определению целой и дробной частей

Допустим противное, пусть

Возможны два случая: b делится на а, и b не делится на а. Если b не делится на а, то из (5) получаем

то есть b делится на а, что невозможно.

Если же b делится на а, то

По условию а отлично от нуля. Полученное противоречие доказывает, что

Докажем теперь второе неравенство леммы. Пусть b не делится на а. Допустим противное,

Но это означает, что b делится на a. Полученное противоречие доказывает, что если b не делится на а, то

Доказанная лемма позволяет из соотношения (4) найти

и в случае, если b не делится на а

Тогда все целочисленные решения уравнения (3) удовлетворяют оценке

AxD,

и уравнение (3) можно решить простым перебором, беря по очереди целые значения х от А до D, вычисляя соответствующие

и проверяя, является ли найденное значение у целым. Если d–bx делится на ax+c, то существует решение

Случай 2. Пусть b делится на а. Тогда границы целочисленных х равны

Тогда F удовлетворяет соотношению

Учитывая, что в этом случае b делится на а, получаем:

Тогда G удовлетворяет соотношению

Учитывая, что в этом случае b делится на а, получаем:

Тогда все целочисленные решения уравнения (3) удовлетворяют оценке

MxN,

и уравнение (3) можно решить простым перебором, беря по очереди целые значения х от А до D, вычисляя соответствующие

и проверяя, является ли найденное значение у целым. Если d–bx делится на ax+c, то существует решение

Итак, оба случая рассмотрены, осталось написать программу для персонального компьютера.

Нелинейные диофантовы уравнения Методическая разработка учителя Поляковой Е. А. — презентация

Презентация была опубликована 6 лет назад пользователемКирилл Ашанин

Похожие презентации

Презентация на тему: » Нелинейные диофантовы уравнения Методическая разработка учителя Поляковой Е. А.» — Транскрипт:

1 Нелинейные диофантовы уравнения Методическая разработка учителя Поляковой Е. А.

2 Решение уравнений в целых или в натуральных числах одна из наиболее древних задач математической науки, важная и для современной математики. Существенной особенностью таких уравнений является наличие в одном уравнении нескольких переменных. Задача состоит в следующем: для заданного уравнения надо найти все целые или натуральные значения переменных, входящих в уравнение, при которых оно превращается в истинное равенство.

3 В истории математики задача решения уравнений в натуральных числах связывается с именем древнегреческого математика Диофанта, придумавшего для таких уравнений много разнообразных приёмов решения, и поэтому их называют диофантовыми. Так же называют и уравнения в целых числах. Ввиду бесконечного разнообразия диофантовых уравнений общего алгоритма их решений не существует, и практически для каждого уравнения приходится изобретать индивидуальный приём.

4 Простейший приём их решения перебор, который всегда пытаются сократить с помощью дополнительных соображений. Решение. Так как обе переменные входят в уравнение в чётных степенях, то достаточно найти только натуральные решения, а затем в полученных решениях произвольным образом поставить знаки. Пример 1. Решить уравнение 2 x² + y² = 267 в целых числах. Вначале ограничим объём перебора заметим, что 2 х²

5 х² х²2 х² у²у² у 135 Из этой таблицы видно, что данное уравнение имеет решения (±7, ±13) и (±11, ±5), или подробнее : (7, 13), (7, 13), (7, 13), (7, 13), (11, 5), (11, 5), (11, 5), (11, 5).

6 Можно было бы заметить, что в любом решении данного уравнения число у должно быть нечётным, т. е. у = 2z 1, и переписать уравнение в виде 2 х² + (2z 1)² = 267, 2x² + (4z² 4z + 1) = 267, x² + 2z² 2z = 133. Из последнего равенства следует, что число х также нечётное, и теперь понадобится перебор всего 6, а не 11 значений х, как в приведённом решении.

7 Ответ:(1 + 2 n; 23n), nцелое число. Пример 2. Решить уравнение 2x ³ + 3y² = 397 в целых числах. Решение. Вначале ограничим объём перебора заметим, что 3 у²

8 Очевидно, что в уравнении одно решение: (5;7). у² у²3 у² х³2 х³ х³х³ х 5

9 Решение. Заметим, что 1 = 1 1 = 1 (1). Значит, возможны варианты: Рассмотрим другие способы решения нелинейных диофантовых уравнений. Пример 3. Решить уравнение (х 2)(х у + 4) = 1 в целых числах. 1) х 2 = 1, тогда х = 3, значит 3 у + 4 = 1, у = 1; 2) х 2 = 1, тогда х = 1, значит у + 4 = 1, у = 5. Ответ: (3; 1); (1; 5).

10 Пример 4. Решить уравнение 2 х² + х у = х + 7 в целых числах. Решение. Перепишем заданное уравнение в виде 2 х² + х у х = 7, х (2 х + у 1) = 7. Заметим, что 7 = 1 7 = 1 (7) = 7 1 = 7 (1) Значит, возможны варианты: 1) х = 1, у 1 = 7, у = 6; 3) х = 7, 14 + у = 1, у = 12. 2) х = 1, 2 + у 1 = 7, у = 4. 4) х = 7, 14 + у 1 = 1, у = 14. Ответ: (1; 6); (1; 4), (7; 12), (7; 14).

11 Пример 5. Решить уравнение х² х у х + у = 1 в целых числах. Решение. Перепишем заданное уравнение в виде х ( х у ) ( х у ) = 1, (х у )( х 1) = 1. Заметим, что 1 = 1 1 = 1 (1). Значит, возможны варианты: 1) х 1 = 1, тогда х = 2, значит 2 у = 1, у = 1; 2) х 1 = 1, тогда х = 0, значит 0 у = 1, у = 1. Ответ: (2; 1); (0; 1).

12 Пример 6. Решить уравнение х² 3 х у = х 3 у + 2 в целых числах. Решение. Перепишем заданное уравнение в виде х 3 ху х + 3 у = 2, х ( х 1 ) 3 у( х 1 ) = 2, (х 1)( х 3 у) = 2. Заметим, что 2 = 1 2 = 2 1 = 1 (2) = 2 (1). 1) х 1 = 1, тогда х = 2, у = 0; 3) х 1 = 1, тогда х = 0, у = 2/3; Ответ: (2; 0); (1; 0). 2) х 1 = 2, тогда х = 3, у = 2/3; 3) х 1 = 2, тогда х = 1, у = 0.

13 Пример 7. Решить уравнение у² 2 х у = 2 х + 6 в целых числах. Ответ: (0; 0); (3; 1). Ответ: (1; 4); (3; 6), (1; 2), (3; 0). Пример 8. Решить уравнение 3 у + 3 х у + 2 х = 0 в целых числах. Пример 9. Решить уравнение у + 2 х у + 4 х = 0 в целых числах. Ответ: (0; 0); (1; 4).

14 Ответ: (0; 0); (2; 2). Ответ: (0; 2); (4; 2), (2; 4), (2; 0). Пример 12. Решить уравнение 2 у² 3 х у + х² = 3 в целых числах. Пример 10. Решить уравнение у + х = х у в целых числах. Пример 11. Решить уравнение у х = х у + 2 в целых числах. Ответ: (5; 2); (1; 2), (5; 2), (1; 2). Задания для самостоятельного решения

Диофантовы уравнения — методы, алгоритмы и примеры решения

Основные понятия

Решением линейных уравнений начали заниматься ещё в Древнем Вавилоне и Греции. Особого успеха в их вычислении смог добиться древнегреческий философ и математик правителя Греции — Диофант Александрийский. В третьем веке до нашей эры он издал свой труд под названием «Арифметика», в котором описал возможные решения различных математических задач. Большая часть их была посвящена уравнениям, которые и были позже названы в его честь.

Диофантовыми уравнениями принято называть линейные выражения вида: a1x1 + a2x2 + … + anxn = c. В этих равенствах икс обозначает искомое неизвестное, а коэффициенты a и c являются целыми числами. Греческий учёный предложил несколько способов решения таких уравнений:

• полный перебор;
• разложение на множители;
• выражение одной переменной через другую с выделением целой части при решении системы;
• поиск частного решения;
• алгоритм Евклида;
• геометрический метод.

Методы решения диофантовых уравнений позволяют найти целые или рациональные решения для алгебраических равенств или их систем. Но при этом число переменных в выражении не должно превышать двух. Как правило, такие уравнения имеют несколько решений, поэтому их другое популярное название — неопределённые.

Чтобы воспользоваться способами, предложенными математиком при рассмотрении задач, нужно попробовать проанализировать исходные данные и свести их к линейному равенству или системе уравнений. При этом коэффициенты, как стоящие возле неизвестных, так и свободные, должны быть целыми. Ответом же должно получиться тоже целое число, обычно натуральное.

Чтобы понимать возможности применения уравнений в тех или иных исследовательских вычислениях, необходимо предварительно ответить на два вопроса: могут ли быть у задания целочисленные решения и ограничено ли число действительных ответов. Поэтому использование способов подходит только для простейших уравнений первой и второй степени. Для выражений высших порядков, например, 4x 3 + 6Y 3 — 2z 4 = 23, определить, является ли решением целое число, довольно проблематично.

Методы решения

Для начала следует рассмотреть однородное линейное уравнение вида: ax + by = 0. Это простой многочлен первой степени. Для него характерно то, что если для коэффициентов можно подобрать один делитель, то обе части возможно сократить на его величину не нарушив принципы записи. Наиболее простым способом определить этот делитель является метод разработанный великим математиком своего времени Евклидом.

Решение диофантовых уравнений по алгоритму Евклида заключается в нахождении общего делителя натуральных чисел с использованием деления с остатком. Для этого нужно взять большее число и просто разделить его на наименьшее. Затем полученный остаток нужно снова разделить на меньшее из чисел. Это действие необходимо повторять до тех пор, пока результатом операции не станет единица, то есть выполнится деление без остатка. Последнее полученное число и будет являться наибольшим общим делителем (НОД).

Существует три теоремы, которые используются при решении уравнений первой степени:

1. В случае, когда НОД равняется единице, выражение будет обязательно иметь хотя бы одну пару целого решения.
2. Если коэффициенты выражения больше единицы, и при этом свободный член нельзя нацело разделить на них, то корни равенства не имеют целого значения.
3. Когда коэффициенты равняются единице, все решения, состоящие из целых чисел, находятся с помощью формул: x = x0c + bt и y = y0c — at, где: х0, y0 — целые ответы, t — множество чисел.

Например, пусть есть равенство вида 54x + 37y = 1. Используя то, что a = 54, а b =37, можно записать: 54 — 37 *1 = 17. Теперь можно выполнить следующие вычисления:

• 37 — 17 * 2 = 3;
• 71 — 3 * 5 = 2;
• 3 — 2 * 1 = 1.

Далее нужно выразить значения коэффициентов через остаток:

• 3 — (17 — 3 * 5) = 1;
• 1 = 17 — 3 * 4;
• 1 = 17 — (37- 17 * 2) * 4;
• 1 = 17 — 37 * 4+17 * 8;
• 1 = 17 * 9 — 37 * 4;
• 1 = (54 — 37 * 1) * 9 — 37 * 4;
• 1 = 54 * 9 — 37 * 9 — 37 * 4;
• 1 = 54 * 9 — 37 * 13;
• 1 = 54х + 37у.

Исходя из приведённого следует, что x0 равняется девяти, а игрек нулевой — минус тринадцать. Таким образом, рассматриваемое уравнение будет иметь вид:

Этим же способом можно и определить, что целых решений в выражении быть не может, как, например, для равенства 17x + 36y = 7. В этом случае НОД не делится на два, поэтому и целых решений нет.

Способ подбора и разложения

Метод подбора используется для нахождения корней простых уравнений. Пожалуй, это самый простой способ, но вместе с тем и требующий повышенного внимания и большого количества операций. Его суть заключается в полном переборе всех допустимых значений переменных, входящих в равенство. Например, эта задача которая будет интересна и школьникам, только знакомящимся с уравнениями.

Пусть имеется зоопарк, в котором находятся птицы и млекопитающие. Всего у животных двадцать лап. Определить, какое количество может быть птиц, а какое — млекопитающих. Для нахождения ответа методом перебора следует принять число одних животных, равное x (пусть это будут четырёхпалые), а других — y (птицы). Таким образом, получится уравнение: 2x + 4 y = 20. Для простоты выражение можно упростить, сократив на два: x + 2y = 10.

Полученное выражение нужно преобразовать, разделив неизвестные знаком равно: x = 10 — 2y. Зная, что ответом могут быть только целые числа, вместо y нужно пробовать подставлять возможные варианты: 1 — 8; 2 — 6; 3 — 4; 4 — 2; 5 — 0. Это и есть все возможные ответы на поставленную задачу.

Разложение выражения на множители можно выполнять различными способами. Вот основные из них:

• вынесение общего множителя: если каждый член многочлена можно разделить на одно и то же число, то его можно вынести за скобку;
• использование формулы сокращённого умножения: оно выполняется по формуле: an — bn = (a-b) * (an-1 + an-2 * b +… a2bn-3 + abn-2 + bn-1);
• применение свойства полного квадрата: это самый эффективный способ, заключающийся в вынесении полного квадрата за скобку с последующим использованием формул разности квадратов;
• группировкой — в его основе лежит вынесение общего множителя таким образом, чтобы появилась возможность перегруппировки выражения, после которой получится значение, присутствующее во всех членах равенства.

Например, пусть имеется нелинейное уравнение вида: 8×4 + 32×2 = 8. Все его члены можно перенести в одну сторону, а равенство приравнять к нулю, при этом сократив каждый член на восемь: x4 + 4×2 — 1 = 0. Для преобразования такого выражения удобнее всего применить метод квадратов. Таким образом, уравнение можно расписать следующим образом: x4 + 2 * 2 * x2 + 4 — 4 — 1 = (x2 + 2)2 — 5 = (x2 + 2 — √5) * (x2 + 2 +√5).

Геометрический подход

Этот метод удобно применять для системы уравнений. Его принцип построен на изображении графиков уравнений и определения их точки пересечения. При этом координаты этой точки и будут являться корнями рассматриваемой системы.

Из этого утверждения можно сделать следующие выводы:

• если графики уравнений представляют пересекающиеся прямые, то решением будет только одно число;
• когда графики уравнений не имеют общих точек, то решения у системы уравнений нет;
• в случае, когда графики совпадают, система будет иметь бесконечное множество корней.

Применять этот метод можно для уравнений, порядок которых не превышает единицы. В равенствах высшего порядка построить график обычно сложно. Например, дана система:

Из первого и второго равенства можно выразить одно неизвестное через другое, используя несколько произвольных чисел. Затем, подставляя их вместо неизвестного, можно построить график. Как только две прямые будут построены, можно будет определить, что точка их пересечения имеет координаты -2; 5. Эти значения и будут искомыми корнями.

Занимательная задача

На самом деле примеры диофантовых уравнений можно встретить в повседневной жизни. Например, при покупке чего-либо в магазине. На эту тему математики смогли придумать интересные задачи, обычно предлагающиеся ученикам на дополнительных занятиях.

Вот одна из них, появившаяся из реальной истории. Однажды математик пришёл в магазин приобрести свитер. Его цена составляла 19 рублей. У учёного же были с собой только купюры номиналом три рубля, а у кассира — пятирублёвки. Задача состоит в том, чтобы выяснить, сможет ли состояться сделка. Иными словами, необходимо найти, сколько нужно математику дать купюр, и какое их количество он получит от кассира.

Рассуждать нужно следующим образом. В задачи есть два неизвестных: количество трёхрублёвых и пятирублёвых купюр. Поэтому можно составить уравнение: 3x — 5y = 19. По сути, уравнение с двумя неизвестными может иметь бесчисленное число решений, но не всегда из них может найтись хотя бы одно целое положительное.

Итак, зная, что неизвестные должны быть целыми положительными числами, нужно выразить неизвестное с меньшим коэффициентом через остальные члены. Получится равенство: 3 x = 19 + 5 y. Левую и правую часть можно разделить на три, а после выполнить простейшие преобразования: x = (19 + 5y) / 3 = 6 + y + (1 + 2y) / 3. Учитывая, что неизвестные и свободный член это целые числа, выражение (1 + 2y) / 3 можно заменить буквой r, также являющимся каким-то целым числом.

Тогда уравнение можно переписать как x = 6 + y + t. Отсюда t = (1 + 2y) / 3 или y = t + (t — 1) / 2. Снова можно сделать вывод, что (t — 1) / 2 — какое-то целое число. Если заменить его на t1, выражение примет вид: y = t + t1.

Подставив t = 2t1 + l в равенство можно получить, что x = 8 + 5t1, а y = 1 + 3t1. Таким образом, решением уравнения будут полученные равенства. Исходя из того, что результат должен быть положительным, равенства можно переписать в неравенства вида:8 + 5t1> 0, 1 + 3t1 > 0. Отсюда определить диапазон, ограничивающий t1. Беря во внимание только плюсовую часть диапазона, можно сделать заключение, что возможные варианты решения лежать в пределе от нуля до плюс бесконечности.

Подставляя по очереди числа, можно определить значения x и y. Искомый ряд будет выглядеть следующим образом: 1 = 8, 13, 18, 23, …, n; <у = 1 + 3t>1 = 1, 4, 7, 10,…, m. То есть математик, дав восемь купюр, получит одну на сдачу, а если он отдаст 13 купюр, то продавец должен будет ему выдать четыре пятирублёвки. Этот ряд можно продолжать до бесконечности.

Использование онлайн-калькулятора

Существуют сайты, рассчитывающие линейные уравнения в автоматическом режиме. Они называются математическими онлайн-калькуляторами. Пользователю, желающему воспользоваться их услугами, нужно иметь лишь подключение к интернету и любой веб-браузер.

Свои услуги сервисы предоставляют бесплатно. При этом часто на их страницах содержится краткий теоретический материал, посвящённый решению диофантовых уравнений. Кроме того, пользователю предоставляется возможность ознакомиться с решением типовых примеров.

Из нескольких десятков таких сайтов на русском языке можно отметить следующие:

Все приведённые сайты имеют интуитивно понятный интерфейс и бесплатны. После того как пользователь введёт в предложенную форму нужные уравнения и запустит расчётчик, онлайн-сервисы не только выдадут ответ, но и выведут на экран пошаговое решение с объяснениями. Таким образом, эти сервисы помогают не только быстро и верно найти решение, но и дают возможность пользователю понять принципы вычисления, проверить самостоятельно выполненный расчёт.