1 1 1 1 1 1 1 1 1 1 Рейтинг 4.35 (17 голосов)

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

Коэффиценты через пробел в уравнении Ax+By=C
Результат решения диофантового уравнения
Уравнение
Корни такого уравнения следующие
Переменная X
Переменная X

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

линейное уравнение

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

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

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

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

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

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

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

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

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

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

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

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

\frac{3}{3}x+\frac{5}{3}y=>x+y

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

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

[3x+5y=1001]- [3(x+y=k)]

Получим

2y=1001-3k

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

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

\frac{2}{2}y+\frac{3}{2}k=y+k

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

[2y+3k=1001]- [2(y+k)]

Получаем  

k=1001

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

2y=1001-3k

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

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

задача на диофантовое уравнение

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

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

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

x=2002-5k

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

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

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

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

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

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

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

\begin{cases}x_t=c a^{\phi(b)-1}+b t,\\ y_t=c\frac{1-a^{\phi(b)}}{b}-a t,\end{cases}

где \phi() - функция Эйлера, которую мы уже умеем расчитывать. Вручную  возводить в степень не самое приятное решение, тем более что значение функции Эйлера может быть велико, но нам это и  не надо.  Нам достаточно посчитать остаток , от (ca^{\phi(b)-1})mod (b) и это тоже мы уже можем делать.

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

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

51x-23y=324

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

 

Результат решения диофантового уравнения
Уравнение
Корни такого уравнения следующие
Переменная X
Переменная X

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

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

Уравнение

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

Переменная X

Переменная X

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

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

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

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

Удачных расчетов!