Линейные диофантовы уравнения онлайн
Линейным диофантовым уравнением с двумя неизвестными называется уравнение вида:
В основе нашего калькулятора лежит расширенный алгоритм Евклида, записанный в виде цепной дроби. Однако, в некоторых случаях (например, когда коэффициент ) применяются более простые подходы. Также калькулятор не рассматривает случаи, когда хотя бы один из коэффициентов или равен , так как они приводят к обычному линейному уравнению.
Если коэффициент не делится нацело на , то линейное диофантово уравнение с двумя неизвестными не имеет решений. Напротив, если делится нацело на , то указанное уравнение имеет бесконечное множество целых решений.
Для решения линейного диофантового уравнения с двумя неизвестными сначала необходимо найти частное решение и , а затем записать общее решение, используя формулы:
Рассмотрим пример решения линейного диофантового уравнения с двумя неизвестными:
Поскольку делится нацело на , то данное уравнение имеет решения в целых числах.
Далее, найдём какое-нибудь конкретное (частное) решение и исходного уравнения. Для этого, сначала необходимо найти частное решение и вспомогательного уравнения с коэффициентом :
а затем умножить найденное частное решение и вспомогательного уравнения на и получить частное решение и исходного уравнения:
Чтобы найти частное решение вспомогательного уравнения используем цепные дроби. Для этого составим дробь , числителем которой будет коэффициент , а знаменателем коэффициент .
Преобразуем данную дробь в цепную дробь:
В полученной цепной дроби отбросим последнюю дробь :
Полученная дробь является отношением частных решений и выбранных с правильным знаком:
Подставляя четыре значения во вспомогательное уравнение, определяем его частное решение:
Теперь, чтобы найти частное решение и исходного уравнения, умножим найденное частное решение и вспомогательного уравнения на :
Используя формулы для общего решения, запишем конечный ответ:
Наш онлайн калькулятор может решить любое линейное диофантово уравнение с двумя неизвестными с описанием подробного хода решения на русском языке. Чтобы начать работу, необходимо ввести уравнение и задать искомые переменные.
Линейные диофантовы уравнения с двумя переменными
Калькулятор решает линейные диофантовы уравнения с двумя переменными.
Сначала калькулятор, теория под ним.
Линейные диофантовы уравнения с двумя переменными
Диофантово уравнение с двумя неизвестными имеет вид:
где a, b, c — заданные целые числа, x и y — неизвестные целые числа.
Для нахождения решений уравнения используется Расширенный алгоритм Евклида (исключая вырожденный случай, когда a = b = 0 и уравнение имеет либо бесконечно много решений, либо же не имеет решений вовсе).
Если числа a и b неотрицательны, тогда с помощью расширенного алгоритма Евклида мы можем найти их наибольший общий делитель g, а также такие коэффициенты и , что:
.
Утверждается, что если число c делится на g, то диофантово уравнение имеет решение; в противном случае диофантово уравнение решений не имеет. Это следует из очевидного факта, что линейная комбинация двух чисел по-прежнему должна делиться на их общий делитель.
То есть если c делится на g, тогда выполняется соотношение:
т. е. одним из решений диофантова уравнения являются числа:
Если одно из чисел a и b или они оба отрицательны, то можно взять их по модулю и применить к ним алгоритм Евклида, как было описано выше, а затем изменить знак найденных коэффициентов и в соответствии с настоящим знаком чисел a и b соответственно.
Если мы знаем одно из решений, мы можем получить выражение для всех остальных решений, которых бесконечное множество.
Итак, пусть g = НОД (a,b), выполняется условие:
.
Тогда, прибавив к число и одновременно отняв от , мы не нарушим равенства:
Этот процесс можно повторять сколько угодно, т. е. все числа вида:
,
где k принадлежит множеству целых чисел, являются множеством всех решений диофантова уравнения.
Частное решение диофантового уравнения с несколькими неизвестными
Ax+By+. Cw+Ez=F |
Коэффициенты диофантового уравнения и свободный член (через пробел) |
Исходное диофантовое уравнение |
Частное решение этого уравнения |
Возвращаясь к ранее написанным статьям, по диофантовым уравнениям
пришло некоторое переосмысление написанного, и готов представить быстрый поиск частого решения любой сложности ( с многими переменными) линейного диофантового уравнения.
Решение немного отличается от того, что можно найти в сети.
Описательная часть алгоритма будет чуть позже.
Проверять правильность калькулятора с проверкой решения уравнения с двумя неизвестными не стоит.
Для этого есть калькулятор упомянутый в самом начале статьи, а этот калькулятор предназначен именно для решения с многими переменными ( тремя, десятью, двадцатью и т.д)
http://planetcalc.ru/3303/
http://abakbot.ru/online-16/480-diofn