Диофантово уравнение с N неизвестными

[i.komarov]

Есть следующее задание: написать программу, которая будет решать линейное диофантово уравнение с произвольным числом неизвестных. На данный момент активно ищу материалы по теме алгоритмов, но ничего особо нет. Может быть кто-то подскажет, в какую сторону копать? Для двух переменных все просто, для N лектор объяснял что-то про "сокращение количества переменных", но понял мало кто.

UPD: Решение сводится к последовательному приведению уравнения от:
$a^{}_{1}*x^{}_{1} + ... + a^{}_{n}*x^{}_{n} = c^{}_{1}$
к:
$a^{}_{1}*x^{}_{1} + ... + a^{}_{1}*x^{}_{n} = c^{}_{1} - (b^{}_{2}*x^{}_{2} + ... + b^{}_{n}*x^{}_{n})$
после чего идет логичная замена:
$c^{}_{1} - (b^{}_{2}*x^{}_{2} + ... + b^{}_{n}*x^{}_{n}) = a^{}_{1} * t^{}_{1}$
что позволяет привести уравнение к следующему виду:
$a^{}_{1}*x^{}_{1} + ... + a^{}_{1}*x^{}_{n} = a^{}_{1} * t^{}_{1}$
и благополучно свести его к новому:
$x^{}_{1} + ... + x^{}_{n} = t^{}_{1}$

Но это мало чем помогает (как мне кажется) в процессе аналитического решения.

[dimkadimon]

Вроде Матиясевич доказал что у общего диофантового уравнения нет алгоритмического решения:

https://ru.wikipedia.org/wiki/%D0%94%D0 ... 1%82%D0%B0

[worm2]

Не, тут только линейные, это гораздо проще.
Вот тут разбирается пример с тремя неизвестными, может быть, что-то прояснит.

[Andrey A]

Если $a_1,a_2,...,a_n$ имеют общий делитель $>1$, который не делит $c_1$, то уравнение неразрешимо, и любая программа должна начать с этого. Если же $a_1,a_2,...,a_n$ взаимно просты, то среди них найдется пара вз. простых, для определенности $a_1,a_2$. Тогда переменные $x_3,...,x_n$ объявляются свободными аргументами, и дело сводится к диофантову уравнению с двумя неизвестными. Зачем еще усложнять?

[ex-math]

Andrey A
Это не так, например $a_1=6$, $a_2=10$, $a_3=15$.

Но судя по дате старт-поста советы уже неактуальны.

[Andrey A]

Да, Вы правы. Сейчас подумаю, самому интересно.

[ex-math]

В вычислительном плане проще всего действовать по аналогии с алгоритмом Евклида.
Выбирается наименьший по модулю коэффициент, скажем, $a_1$, и остальные делятся на него с остатком. Получится $a_1(x_1+q_2x_2+\ldots+q_nx_n)+r_2x_2+\ldots+r_nx_n=b$. Выражение в скобках заменяется на новую переменную и история повторяется до тех пор, пока один из коэффициентов не станет равным единице. Тогда соответствующую переменную можно выразить через остальные (они будут произвольными целыми). Ну и обратный ход чтобы вернуться к иксам.

-- 20.08.2017, 13:51 --

Если же интересна общая картина, то проще перенести одну неизвестную вправо и сводить к уравнению с числом неизвестных на одну меньше (по индукции). Окажется, что множество решений -- всегда $(n-1)$-мерная решетка.

[Andrey A]

ex-math
Уравнение $6x_1+10x_2+15x_3=c$ я бы переписал где-нибудь так: $2x_2+3x_3=\dfrac{c-6x_1}{5}$. Разница в том, что $x_1$ тут уже не свободный аргумент, а сравнимый $\equiv \dfrac{c}{6}\mod 5$. $6$ и $5$ вз. просты по условию, сравнение разрешимо для любого $c.$ Но это для $n=3.$ Для большего количества переменных вместо уравнения получаем сравнение с $n-2$ неизвестными, ту же по сути задачу. Тогда я не прав. Если есть иные подходы, это актуально (как-то не думал о подобных раскладах). Спасибо. Ага, Вы что-то уже предложили.

[Andrey A]

ex-math в сообщении #1241923 писал(а):

... по аналогии с алгоритмом Евклида.
$a_1(x_1+q_2x_2+\ldots+q_nx_n)+r_2x_2+\ldots+r_nx_n=b$.

Идею понял, хотя тут могут быть неожиданности. Больше это напоминает деление лесенкой, и не очень понятно почему в конце должна случиться единица. Например, в уравнении $55x_1+95x_2+209x_3=m$, делая замену $y_1=x_1+x_2+3x_3$, получаем новое уравнение $55y_1+40x_2+44x_3=m$ и после замены $y_2=x_2+x_3$ остается четверка перед $x_3$. Можно конечно продолжить процесс, но упрощенной системы с гарантированно целыми решениями тогда лишаемся. Надо еще подумать.

[g______d]

Даже если у нас не одно уравнение, а система, это не намного сложнее по сравнению с системами линейных уравнений над полем, т. е. обычной линейной алгеброй.

https://www.math.uwaterloo.ca/~wgilbert ... athria.pdf

(текст выбран более-менее случайно)

[mihailm]

Кратко про целочисленные решения СЛАУ написано в задачнике Кострикина - 8.23 в конце 2-й главы.

[Andrey A]

Спасибо за ссылки.

[ex-math]

Andrey A
Единица получится потому, что на каждом шаге минимальный коэффициент строго уменьшается. На каждом шаге уравнения равносильны, поэтому мне непонятно, чего мы "лишились" в Вашем примере.

-- 21.08.2017, 10:18 --

А, Вы не так сделали замену, надо $y_2=y_1+x_2+x_3$.
Кстати, можно делить не только с недостатком, но и с избытком. Например, $y_1=x_1+2x_2+4x_3$ даст $55y_1-15x_2-11x_3=m$, что быстрее приведет к цели. Правую часть тоже можно делить, вводя в замены свободный член.

[Andrey A]

ex-math в сообщении #1242074 писал(а):

Кстати, можно делить не только с недостатком, но и с избытком.

Как в непрерывных дробях - можно брать не остатки, а абсолютно наименьшие вычеты. Это несколько ускоряет процесс, но по сути ничего не меняет.

ex-math в сообщении #1242074 писал(а):

Единица получится потому, что на каждом шаге минимальный коэффициент строго уменьшается.

То есть продолжаем процесс до единицы и получаем полную систему $n$ уравнений с $n$ неизвестными. Тогда всё понятно кроме одного: почему определитель системы $\Delta$ должен быть $=1 $, и не придется ли в противном случае решать сравнение по $\mod \Delta$ чтобы получить целые решения? Вопрос не праздный. Можно ведь и сразу заняться сравнением (как в примере выше), не решая никаких систем.

p.s. Я к тому, что последняя переменная (с единицей) может оказаться уже не из $x$-ов. Но даже если из $x$-ов, получим полную систему $n-1$ уравнений.

(Оффтоп)

Надо же, влез не в свою тему....

[ex-math]

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

-- 21.08.2017, 14:38 --

Повторюсь, этот подход удобен для решения, а для построения теории лучше действовать иначе.