2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Диофантово уравнение с N неизвестными
Сообщение09.06.2017, 16:15 


09/06/17
1
Есть следующее задание: написать программу, которая будет решать линейное диофантово уравнение с произвольным числом неизвестных. На данный момент активно ищу материалы по теме алгоритмов, но ничего особо нет. Может быть кто-то подскажет, в какую сторону копать? Для двух переменных все просто, для 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}$

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

 Профиль  
                  
 
 Re: Диофантово уравнение с N неизвестными
Сообщение20.08.2017, 08:00 
Аватара пользователя


01/06/12
971
Adelaide, Australia
Вроде Матиясевич доказал что у общего диофантового уравнения нет алгоритмического решения:

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

 Профиль  
                  
 
 Re: Диофантово уравнение с N неизвестными
Сообщение20.08.2017, 09:27 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Диофантово уравнение с N неизвестными
Сообщение20.08.2017, 11:11 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Диофантово уравнение с N неизвестными
Сообщение20.08.2017, 11:30 
Заслуженный участник
Аватара пользователя


24/02/12
1842
Москва
Andrey A
Это не так, например $a_1=6$, $a_2=10$, $a_3=15$.

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

 Профиль  
                  
 
 Re: Диофантово уравнение с N неизвестными
Сообщение20.08.2017, 12:02 
Заслуженный участник
Аватара пользователя


21/11/12
1244
Санкт-Петербург
Да, Вы правы. Сейчас подумаю, самому интересно.

 Профиль  
                  
 
 Re: Диофантово уравнение с N неизвестными
Сообщение20.08.2017, 13:46 
Заслуженный участник
Аватара пользователя


24/02/12
1842
Москва
В вычислительном плане проще всего действовать по аналогии с алгоритмом Евклида.
Выбирается наименьший по модулю коэффициент, скажем, $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)$-мерная решетка.

 Профиль  
                  
 
 Re: Диофантово уравнение с N неизвестными
Сообщение20.08.2017, 13:53 
Заслуженный участник
Аватара пользователя


21/11/12
1244
Санкт-Петербург
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$ неизвестными, ту же по сути задачу. Тогда я не прав. Если есть иные подходы, это актуально (как-то не думал о подобных раскладах). Спасибо. Ага, Вы что-то уже предложили.

 Профиль  
                  
 
 Re: Диофантово уравнение с N неизвестными
Сообщение20.08.2017, 22:47 
Заслуженный участник
Аватара пользователя


21/11/12
1244
Санкт-Петербург
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$. Можно конечно продолжить процесс, но упрощенной системы с гарантированно целыми решениями тогда лишаемся. Надо еще подумать.

 Профиль  
                  
 
 Re: Диофантово уравнение с N неизвестными
Сообщение20.08.2017, 23:15 
Заслуженный участник
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Диофантово уравнение с N неизвестными
Сообщение20.08.2017, 23:22 


19/05/10

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

 Профиль  
                  
 
 Re: Диофантово уравнение с N неизвестными
Сообщение20.08.2017, 23:57 
Заслуженный участник
Аватара пользователя


21/11/12
1244
Санкт-Петербург
Спасибо за ссылки.

 Профиль  
                  
 
 Re: Диофантово уравнение с N неизвестными
Сообщение21.08.2017, 10:12 
Заслуженный участник
Аватара пользователя


24/02/12
1842
Москва
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$, что быстрее приведет к цели. Правую часть тоже можно делить, вводя в замены свободный член.

 Профиль  
                  
 
 Re: Диофантово уравнение с N неизвестными
Сообщение21.08.2017, 11:13 
Заслуженный участник
Аватара пользователя


21/11/12
1244
Санкт-Петербург
ex-math в сообщении #1242074 писал(а):
Кстати, можно делить не только с недостатком, но и с избытком.

Как в непрерывных дробях - можно брать не остатки, а абсолютно наименьшие вычеты. Это несколько ускоряет процесс, но по сути ничего не меняет.
ex-math в сообщении #1242074 писал(а):
Единица получится потому, что на каждом шаге минимальный коэффициент строго уменьшается.

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

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

(Оффтоп)

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

 Профиль  
                  
 
 Re: Диофантово уравнение с N неизвестными
Сообщение21.08.2017, 14:37 
Заслуженный участник
Аватара пользователя


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

-- 21.08.2017, 14:38 --

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.

Модераторы: Karan, maxal, Toucan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group