Решение диофантовых уравнений онлайн калькулятор

Линейным диофантовым уравнением с двумя неизвестными называется уравнение вида:

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

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

Для решения линейного диофантового уравнения с двумя неизвестными сначала необходимо найти частное решение и , а затем записать общее решение, используя формулы:

Рассмотрим пример решения линейного диофантового уравнения с двумя неизвестными:

Поскольку делится нацело на , то данное уравнение имеет решения в целых числах.

Далее, найдём какое-нибудь конкретное (частное) решение и исходного уравнения. Для этого, сначала необходимо найти частное решение и вспомогательного уравнения с коэффициентом :

а затем умножить найденное частное решение и вспомогательного уравнения на и получить частное решение и исходного уравнения:

Чтобы найти частное решение вспомогательного уравнения используем цепные дроби. Для этого составим дробь , числителем которой будет коэффициент , а знаменателем коэффициент .

Преобразуем данную дробь в цепную дробь:

В полученной цепной дроби отбросим последнюю дробь :

Полученная дробь является отношением частных решений и выбранных с правильным знаком:

Подставляя четыре значения во вспомогательное уравнение, определяем его частное решение:

Теперь, чтобы найти частное решение и исходного уравнения, умножим найденное частное решение и вспомогательного уравнения на :

Используя формулы для общего решения, запишем конечный ответ:

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

Видео:Решение диофантовых уравненийСкачать

Линейные диофантовы уравнения с двумя переменными

Калькулятор решает линейные диофантовы уравнения с двумя переменными.

Сначала калькулятор, теория под ним.

Линейные диофантовы уравнения с двумя переменными

Диофантово уравнение с двумя неизвестными имеет вид:

где a, b, c — заданные целые числа, x и y — неизвестные целые числа.

Для нахождения решений уравнения используется Расширенный алгоритм Евклида (исключая вырожденный случай, когда a = b = 0 и уравнение имеет либо бесконечно много решений, либо же не имеет решений вовсе).
Если числа a и b неотрицательны, тогда с помощью расширенного алгоритма Евклида мы можем найти их наибольший общий делитель g, а также такие коэффициенты и , что:
.

Утверждается, что если число c делится на g, то диофантово уравнение имеет решение; в противном случае диофантово уравнение решений не имеет. Это следует из очевидного факта, что линейная комбинация двух чисел по-прежнему должна делиться на их общий делитель.

То есть если c делится на g, тогда выполняется соотношение:

т. е. одним из решений диофантова уравнения являются числа:

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

Если мы знаем одно из решений, мы можем получить выражение для всех остальных решений, которых бесконечное множество.

Итак, пусть g = НОД (a,b), выполняется условие:
.

Тогда, прибавив к число и одновременно отняв от , мы не нарушим равенства:

Этот процесс можно повторять сколько угодно, т. е. все числа вида:

,
где k принадлежит множеству целых чисел, являются множеством всех решений диофантова уравнения.

Видео:Математика. Линейные диофантовы уравнения с двумя неизвестными. Центр онлайн-обучения «Фоксфорд»Скачать

Линейное диофантово уравнение онлайн

Все мы знаем что такое линейное уравнение. Это уравнение вида

Этим уравнением описывается такой геометрический объект как прямая. Если коэффициенты а,b и c известны то всегда можно найти бесконечное множество пар x и y где будет выполнятся равенство.

Что же тогда означает «диофантово»? Это говорит о двух вещах.

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

Названы они в честь математика II– III веков н.э. Диофанта, который занимался терией и практикой решения подобных задач.

Зачем же нам решать такие уравнения? Дело в том что в практических задачах, не все можно делить на дробные части. Людей не поделишь, банкноты 50, 100, 1000 рублей нельзя порвать на кусочки, что бы отдать часть кому то, количество машин не может быть дробным и еще много всего в нашей жизни нельзя делить.

И когда возникает задача найти пару целочисленных значенях в подобном уравнении, мы сталкиваемся с классическим линейным диофантовым уравнением.

В нашей статье мы рассмотрим решение самых простых и часто встречающихся в школьных учебниках уравнений с двумя переменными.

Есть несколько вариантов решения подобных задач. Мы же остановимся только на двух. Первый способ применим, даже для самых маленьких и можно использовать для решения задач в школе. Второй способ, применим для продвинутых пользователей и для нашего бота, который именно основываясь на нём и будет выдавать решения диофантового уравнения.

Возьмем первое попавшееся описание любой задачи «Шехерезада рассказывает свои сказки великому правителю. Всего она должна рассказать 1001 сказку. Сколько ночей потребуется Шехерезаде, чтобы рассказать все свои сказки, если x ночей она будет рассказывать по 3 сказки, а остальные сказки по 5 за у ночей»

Как можно заметить, эта задача выражается вот такой формулой

1. Выделим минимальный коэффицент при неизвестных (не учитывая знак перед ним). Это 3 (три)

2. Разделим каждый элемент уравнения при неизвестных на 3 и выделим целые числа из получившихся в результате деления.

x+y» src=»https://img.abakbot.ru/cgi-bin/mathtex.cgi?%5Cfrac%3C3%3E%3C3%3Ex+%5Cfrac%3C5%3E%3C3%3Ey=%3Ex+y» style=»width: 135px; height: 35px;» />

3. Обзовем полученное выражение какой либо буквой

4. Умножим на 3 каждый элемент и вычтем из исходного уравнения.

5. Проделаем такую же процедуру 1-4 над полученным уравнением. Но так как тут уже одна перменная то становится совсем легко

Делим на два, выделяем целую часть при коэффицентах

Умножаем на два и вычитаем и уравнения из 4 пункта

Подставив в уравнение из пунтка 4 мы сможем найти y

получили что y=-1001

Теперь легко подсчитать чему же равно x, подставив х в исходное уравнение

получаем что x=2002

Таким образом мы получили первую пару целочисленных значений, при которых исходное уравнение верно.

Следующие пары будут подчинятся следующим формулам

где k может быть любым целочисленным значением

Но сама задача не решена, ведь ночей не может быть отрицательное количество.

Пусть k=-334, тогда y=1, а x=332

Это первая пара которая может служить ответом, то есть 1(одну) ночь Шехерезада прочитает 5 сказок, а все другие 332 ночи будет читать по 3 сказки за ночь.

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

Теперь о втором способе

Есть явное решение линейного уравнения и оно вот такое

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

Приступим таким образом сразу к примерам

Найдем решение вот такого уравнения

51x-23y=324

Пишем в строке ввода через пробел 51 -23 324 и получаем ответ

То есть при всех целых k уравнение будет верно.

Давайте рассмотрим еще один пример

Бот нам выдаст ответ

«Ага!» — скажете Вы. «Решение то не правильное». Ведь подставив x и y в начальное уравнение мы не получим равенство.

В чем же ошибка бота? Все дело в том что коэффициенты при неизвестных (3 и 15) имеют общий делитель 3 (три). А как мы знаем 22 на три нацело не делится. Таким образом это уравнение неразрешимо в целых числах.

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

Кто интересуется, а как же решать диофантовые уравнения с тремя неизвестными, пожалуйте сюда

🎦 Видео

Как решать Диофантовы уравнения ★ 9x+13y=-1 ★ Решите уравнение в целых числахСкачать

Диофантовы уравнения x²+xy-y=2Скачать

Решите уравнение в целых числах 3x^2+5y^2=345 ✱ Диофантовы уравнения ✱ Как решать?Скачать

Полезные мелочи | алгоритм Евклида | диофантовы уравнения | примеры | 1Скачать

Классический способ решения Диофантовых уравнений ➜ Решите уравнение в целых числах ➜ 13x-7y=6Скачать

Линейные диофантовы уравненияСкачать

Как решать Диофантовы уравнения ➜ Решите уравнение в целых числах 4x+5y=6Скачать

Диофантовы уравнения x+y=xyСкачать

РЕШАЕМ ДИОФАНТОВОЕ УРАВНЕНИЕ | ПРОСТЫМИ СЛОВАМИСкачать

Алексей Савватеев "Диофантовы уравнения". Лекции 1-2Скачать

ПЕРЕЧНЕВЫЕ ОЛИМПИАДЫ. Диофантовы уравненияСкачать

Решите уравнение в целых числах 5x-4y=3 ➜ Как решать Диофантовы уравнения?Скачать

#86. Делимость и диофантовы уравнения! ТРУДНАЯ ЗАДАЧА!Скачать

Диофантовы уравнения x³-y³=91Скачать

Решите уравнение в целых числах: y²+1=2^x ➜ Как решать диофантовы уравненияСкачать

Как решать уравнения с двумя переменными в целых числах! Лёгкий способ!Скачать

Решите уравнение в целых числах ★ √x+√y=√50 ★ Как решать диофантовы уравнения?Скачать