Решение нелинейных диофантовых уравнений, таких как (8 + 3n) m = 11? - PullRequest
Новая
       16

Решение нелинейных диофантовых уравнений, таких как (8 + 3n) m = 11?

0 голосов
/ 10 октября 2018

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

  • (8 + 3n) m = 11 |n ∈ {0,1}, m ∈ ℤ +

  • (5+ (7 + 3x + 2y) a + 3z) b = 30 |x, y, z ∈ {0,1}, a, b ∈ ℤ +

В идеале я хотел бы иметь возможность генерировать множество всех действительных целочисленных значений для n, mи a, b, x, y, z соответственно.По крайней мере, я хотел бы проверить, можно ли вообще решить уравнения.Учитывая, что эти уравнения являются нелинейными, я мог бы представить, что типичные методы, используемые для решения простых диофантовых уравнений, здесь потерпят неудачу.

Я был бы очень признателен за любую помощь, которую мог получить!

1 Ответ

0 голосов
/ 25 октября 2018

Поскольку число 11 простое, в Z есть только 4 возможных факторизации: 

8+3n=11 and m=1
8+3n=1 (impossible) and m=11
8+3n=-11 (impossible) and m=-1
8+3n=-1 m=-11

При ограничении n в {0,1} остается только одно решение ...

Для второгоВ этом случае возможностей гораздо больше, так как 30 равен 2 * 3 * 5, у вас будет 16 возможных продуктов для двух ваших терминов в Z ...

Если вы замените (x, y, z) на ихИз 8 возможных комбинаций первый член вырождается в полином 1-го порядка по a, так что для проверки целочисленного корня нужно всего 8 * 16 = 128 полиномов.

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

Если факторы остаются многомерными, но линейными (общий порядок 1), то это похоже на решение линейных систем.Но поиск целочисленных решений не обязательно тривиален, я рекомендую прочитать http://sites.math.rutgers.edu/~sk1233/courses/ANT-F14/lec3.pdf

Иначе, если факторы остаются многомерными и имеют общий порядок> 1, что эквивалентно решению полиномиальных систем ... В некоторых случаях это возможно, см.https://en.wikipedia.org/wiki/Gr%C3%B6bner_basis.

...