ФИЗИКО-МАТЕМАТИЧЕСКИЕ НАУКИ

О двух свойствах числа Фробениуса

В. П. Савельев^a, В. Н. Шевченко<sup>b

a</sup> Нижегородский государственный инженерно-экономический университет
^b Нижегородский государственный университет им. Н.И. Лобачевского

Аннотация: Проблема нахождения числа Фробениуса актуальна, она тесно связана с теорией графов и известными задачами о рюкзаке и о размене. Формула для вычисления числа Фробениуса известна лишь для двух чисел: если наибольший общий делитель натуральных чисел $a$ и $b$ равен единице, то $\mathrm{frob}(a,b) = ab - a - b$. В работе доказаны два свойства, касающиеся проблемы нахождения числа Фробениуса для трех натуральных чисел. Первое из этих свойств дополняет, даже можно сказать, обогащает указанную выше знаменитую формулу Фробениуса для двух натуральных чисел. Это свойство позволяет перейти от числа Фробениуса для двух натуральных чисел к числу Фробениуса для трех натуральных чисел, когда третье число является числом Фробениуса для первых двух чисел: $\mathrm{frob}(a,b,\mathrm{frob}(a,b)) = \mathrm{frob} (a,b) - a$. Второе свойство относится к числу свойств “однородности” операции $\mathrm{frob}$, позволяющих в некоторых случаях выносить множитель перед одним или несколькими переменными за знак этой операции. В результате этого свойства проблема нахождения числа Фробениуса для трех чисел специального вида сводится к известной формуле числа Фробениуса для трех последовательных натуральных чисел.

Ключевые слова: аддитивная полугруппа, проблема Фробениуса, число Фробениуса.

DOI: 10.23670/IRJ.2022.123.59