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

[Арсений]

Подскажите пожалуйста, существует ли формула или алгоритм для определения максимального натурального числа, не представимого в виде суммы двух натуральных? Более формально: есть взаимно простые числа $a,b$. Найти максимальное число $s$, которое нельзя представить в виде $s=xa+yb$ где $x,y$ - неотрицательные целые.

Мне известен способ решения этой задачи через диофантовы уравнения - находятся такие $p,q$ что $ap+bq=1$, откуда получается частное решение уравнения $s=ax+by$, затем анализируется семейство $x'=x-bn$, $y=y+an$ на предмет неотрицательных решений. Подскажите пожалуйста, есть ли более простая формула/алгоритм? Как эта задача обобщается на бОльшее количество переменных? Где может быть изложена теория, связанная с этой задачей?

Арсений Трушин.

[Narn]

А чему равно минимальное число $s$, которое можно представить в таком виде? Тут, по-моему, подумать секунд 10-20, и ответ готов, если я правильно понял вопрос.

[nworm]

Тут можете посмотреть
http://mathworld.wolfram.com/CoinProblem.html

[Narn]

Извините, поторопился...

[Арсений]

nworm, огромное спасибо.

[maxal]

Это так называемое число Фробениуса: http://mathworld.wolfram.com/FrobeniusNumber.html