Линейное диофантово уравнение и 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 
8
2 -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.
Диофантовое уравнение с тремя неизвестными
| Коэффиценты через пробел в уравнении Ax+By+Cz=D |
| Результат решения диофантового уравнения с тремя неизвестными | |||
| Целочисленные корни такого уравнения следующие | |||
После того, как автор сайта смог научить своего бота решать Линейное диофантово уравнение онлайн, возникло желание научить бота решать подобные уравнения, но уже с тремя неизвестными. Пришлось окунутся в книги. Вынырнув оттуда через два месяца, автор понял, что он ничего не понял. Зело умные математики, так мудрёно писали алгоритм вывода формул, что мне смертному было стыдно. Опечалился было, но мысль на книжных просторах все таки одну полезную нашел, и с этой мысли пришло понимание как решать диофантовые уравнения с тремя неизвестными. Итак для всех, кто не математик, но хочет им быть 🙂 Диофантовое уравнение с тремя неизвестными имеет вот такой вид где целые числа Если мы подумаем какое же общее решение может быть у неизвестных, то самое банальное выглядит так Подставим наше общее решение в уравнение Какой же от этого прок, спросит нетерпеливый читатель? А вот какой, сгруппируем все по неизвестным,получим Смотрите, в правой части стоит какое то постоянное число, обозначенное буквой d Значит, от t ( она же переменная, мало ли каким она значением хочет стать) оно не зависит а значит Логично предположить что и от z оно не зависит а значит а вот от постоянных значений A3 и B3 оно зависит напрямую , то есть Что же в конечном итоге мы получили? А получили мы три типовых классических диофантовых уравнений с двумя неизвестными, которые решать мы можем легко и непринужденно. В первых строках поисковых систем нашлось вот такое уравнение Первое уравнение будет вот такое Избавимся от нулей, взяв к примеру k=-1. ( Хотите можете взять 2 или 100 или -3) На окончательное решение это не повлияет. Решаем второе уравнение здесь пусть k=0 ( так как X и Y не совпадают уже при нулевых значениях) И последнее третье уравнение Корни тут такие Подставим теперь все найденные значения в общий вид Заметьте, что все решается очень легко и прозрачно! Наверняка преподаватели и способные студенты возьмут себе на вооружение эту методику, так как в книгах автор бота её так и нашел. Еще один пример, уже решенный с помощью бота.
Дополнение: Когда будете решать подобные уравнения с помощью бота, можете столкнуться с тем, что бот Вам выдаст ошибку с просьбой, поменять переменные местами, для другой попытки решить уравнение. Это связано с тем что при промежуточных вычислениях, получается нерешаемое уравнение При попытке решить уравнение мы получим ошибку, так как при любых значениях, в левой части будет всегда(!!) чётное число, а в правой части как мы видим нечетное. Но это не значит что изначальное уравнение нерешаемое. Достаточно поменять слагаемые в другом порядке, например так и получаем ответ
Дополнение от 23 ноября 2015 года Зашел спор как решать уравнение подобное этому Мол, позволяет ли методика которая была описана выше определить существует ли целочисленные решения этому уравнению? Я не могу доказать, но предполагаю, что если при всех циклических перестановках слагаемых как это было показано на примере уравнения у нас получаются нерешаемые линейные уравнения, то такое уравнение нерешаемое. В нашем примере так и получается что при любых переставновках, в левой части линейного уравнения всегда(!) будут НЕ взаимно простые числа, и НОД их не является делителем числа в правой части уравнения ( =8 ) Таким образом утверждается что такое диофантовое уравнение нерешаемое в целых числах, но зато оно решается в случае рациональных дробей при любых значениях z и t уравнение будет верным По горячим следам, окончательное дополнение от 23 нобяря 2015Все таки я ошибся в последнем примере. решаемое оно Так что вышеописанная методика и бот, применим ТОЛЬКО для тех случаев, когда хотя бы одна пара слагаемых из левой части являются взаимно простыми числами. Если конечно не воспользуетесь новым калькулятором который лишен, всех этих недостатков Линейные диофантовы уравнения Линейные диофантовы уравнения и методы их решения в школьном курсе математики не изучаются. Их можно встретить, в основном, лишь в олимпиадных заданиях. В данной работе рассматриваются следующие способы решения линейных диофантовых уравнений: алгоритм Евклида, метод перебора, метод спуска, метод рассмотрения остатков от деления, а также приведены примеры решения линейных диофантовых уравнений с тремя неизвестными. Просмотр содержимого документа |
1, ( Каталана); ах 2 + bxy + су 2 + dx + еу + f = 0 , где а , b , с , d , е , f — целые числа, т. е. общее неоднородное уравнение второй степени с двумя неизвестными (П.Ферма, Дж. Валлис, Л. Эйлер, Ж. Лагранж и К.Гаусс) » width=»640″
