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

[ArtProg]

Интересует точная формула(если такова существует) для числа $N_n$ целых неотрицательных решений уравнения вида $\qquad a_1 \cdot x_1+\dots$ $+a_n \cdot x_n=c, \, \, a_i,c$ - натуральные числа, $i=1 \dots n,$ которая зависела бы только от коэффициентов при неизвестных переменных, ну и свободного коэффициента в правой части уравнения(конечно при условии конечности числа решений). В крайнем случае(если точной формулы не существует) будет полезно хотя бы условие существования таких решений. Вывел только верхнюю оценку (выводится элементарно) и то для случая с двумя переменными: $\qquad a_1 \cdot x_1+a_2 \cdot x_2=c, N_2 \leqslant [c/(a_1 \cdot a_2)]+1$. Для случая же с большим количеством переменных пока что даже верхней оценки не получается, не говоря уже о точной формуле.

[Andrey A]

Известно, что для попарно взаимно простых $ab>c$ в положительных числах разрешимо ровно одно из двух уравнений
$ax+by=c$
$ax+by=ab-c.$
Доказательство где-то было, но мутное. Лучше пробуйте самостоятельно. Кажется, тут https://dxdy.ru/topic85607.html

[ArtProg]

Да уже и в сторону метода Виноградова посматривал , правда мне больше нужна все таки точная(не асимптотическая) формула, или хотя бы условие разрешимости для размерности больше двух. Но спасибо за наводку! Надеюсь кто-то еще выразится по поводу поставленного вопроса.

[Cash]

https://en.m.wikipedia.org/wiki/Coin_problem

[ArtProg]

Интересная ссылка, спасибо! Правда немного не то чего бы я хотел, так как чисел, которые непредставимы линейной суммой и больше заданного числа бесконечно много, и может оказаться, что для конкретного рассматриваемого числа, большего чем соответствующее число Фробениуса, линейное уравнение будет иметь решение, если я конечно правильно расшифровал английский текст.

[Cash]

Да, расшифровка не удалась.

ArtProg в сообщении #1461338 писал(а):

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

верно прямо противоположное. Сумм, которых не представить монетами данных номиналов, конечное количество (НОД номиналов равен 1). Потому и можно определить число Фробениуса - наибольшее из таких сумм.

[kotenok gav]

Cash хочет сказать следующее: пусть у вас есть уравнение $\sum a_ix_i=c$ ($\operatorname{GCD}(\mathbf{a})=1$), тогда, если $c>g(\mathbf{a})$ ($g$ - число Фробениуса), то это уравнение имеет минимум одно решение.

-- 09 май 2020, 20:29 --

Еще, очевидно, уравнение будет иметь решение только если $\operatorname{GCD}(\mathbf{a})\mid c$.

-- 09 май 2020, 20:55 --

По поводу числа Фробениуса: $g(a, b)=ab-a-b$, и в статье https://doi.org/10.1016/j.jnt.2016.05.027 даются формулы (почти все точные) для $g(a, b, c)$ для большинства (или всех, не совсем понял) случаев.

[ArtProg]

Да, перевел невнимательно, каюсь. Но тем не менее непонятно, сколько все таки точно решений будет иметь уравнение, если таковы существуют.
kotenok gav

Цитата:

Cash хочет сказать следующее: пусть у вас есть уравнение $\sum a_ix_i=c$ ($\operatorname{GCD}(\mathbf{a})=1$), тогда, если $c>f(\mathbf{a})$ ($f$ - число Фробениуса), то это уравнение имеет минимум одно решение

Итак, если $c>f(\mathbf{a})$, то по крайней мере одно решение есть, а если $c \leqslant f(\mathbf{a})$, то может и быть а может и нет, правильно? То есть, все таки последний случай требует дополнительных знаний кроме числа Фробениуса, чтобы ответить на вопрос о существовании решения?
Спасибо, ссылку гляну.

[kotenok gav]

ArtProg в сообщении #1461351 писал(а):

правильно?

Да.

[DeBill]

ArtProg в сообщении #1461310 писал(а):

и: $\qquad a_1 \cdot x_1+a_2 \cdot x_2=c, N_2 \leqslant [c/(a_1 \cdot a_2)]+1$. Для случая же с большим количеством переменных пока что даже верхней оценки не получается, не говоря уже о точной формуле.

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

[ArtProg]

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

[Cash]

ArtProg в сообщении #1461351 писал(а):

Да, перевел невнимательно, каюсь. Но тем не менее непонятно, сколько все таки точно решений будет иметь уравнение, если таковы существуют.
kotenok gav

Цитата:

Cash хочет сказать следующее: пусть у вас есть уравнение $\sum a_ix_i=c$ ($\operatorname{GCD}(\mathbf{a})=1$), тогда, если $c>f(\mathbf{a})$ ($f$ - число Фробениуса), то это уравнение имеет минимум одно решение

Итак, если $c>f(\mathbf{a})$, то по крайней мере одно решение есть, а если $c \leqslant f(\mathbf{a})$, то может и быть а может и нет, правильно? То есть, все таки последний случай требует дополнительных знаний кроме числа Фробениуса, чтобы ответить на вопрос о существовании решения?
Спасибо, ссылку гляну.

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

[ArtProg]

Цитата:

Суду все ясно... Ссылки надо не глядеть, а с ними работать.

Ясно тут только одно, что числа Фробениуса не дают ответ для всех случаев. Можете опровергнуть или приведете условия для всех случаев?

Цитата:

Все что нужно, есть в статье Вики, только надо понимать, что это не блюдечко с голубой каёмочкой, а отправная точка.

Ах, Вы меня еще и на Вики отправляете. Спасибо за бесполезный совет.

[vpb]

ArtProg в сообщении #1461310 писал(а):

если такова существует

Это сильно вряд ли.

ArtProg в сообщении #1461310 писал(а):

будет полезно хотя бы условие существования таких решений

Для достаточно больших $c$ условие состоит в том, что $c$ делится на $\text{НОД}(a_1,\ldots,a_n)$. (Необходимость очевидна. Достаточность попробуйте доказать сами по индукции, начав с $n=2$.)

-- 10.05.2020, 01:41 --

ArtProg в сообщении #1461313 писал(а):

Да уже и в сторону метода Виноградова посматривал

Асимптотическую формулу и без Виноградова получить можно.

[kotenok gav]

vpb в сообщении #1461477 писал(а):

Для достаточно больших $c$

И даже можно сказать, насколько: $c>\operatorname{GCD}(\mathbf{a})g(\frac1{\operatorname{GCD}(\mathbf{a})}\mathbf{a})$