Pull to refresh

Метод решения системы диофантовых уравнений

ProgrammingMathematics

Добрый день!


Как и обещал в первой своей статье, я хочу ознакомить Вас с одним из методов решения системы диофантовых уравнений. Цель статьи ознакомить остальных читателей с этой методикой и донести её в более или менее понятном виде.


Рассмотрим систему из двух диофантовых уравнений


image
и


image


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


image


Как проверить что я не лгу?


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


image


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


Следующим этапом мы подставим наше общее решение


image


во второе уравнение


image


Процедура такая же: умножаем вектор из коэффициентов второго уравнения на общее решение первого


получаем вот такой результат


image


то есть мы получили уравнение вида


image


С правой стороны второго диофантового уравнения как был свободный член равный -335, так и остался, то есть наше окончательное решение на этом этапе имеет вид


image


Или перенеся свободные члены в правую сторону получим


image


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


image


то есть общее решение имеет вид


image


А теперь делаем обратное преобразование(пусть так называется). То есть в систему


image


Мы вместо неизвестных x подставляем то, что получилось на последнем этапе


image


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


Результат умножения двух матриц порождает


image


матрицу


image


Последний столбец это свободные члены этой системы.
Учтем тот столбец который временно удаляли, перед умножением и сложим их


image


наш окончательный ответ в виде матрицы


image


Проверим?


Векторное произведение коэффициентов первого уравнения и матрицы


image


а векторное произведение коэффициентов второго уравнения и матрицы


image


Как видим, результат совпадает с свободным членом каждого из уравнений.
Таким образом общее решение имеет вид


image


где m,p,q — могут принимать любые целые значения


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


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


Буду благодарен за замечания, отзывы и предложения.

Tags:диофантовоесистемаматрицауравнений
Hubs: Programming Mathematics
Total votes 9: ↑8 and ↓1+7
Views3.6K

Popular right now

Top of the last 24 hours