for any coprime numbers a and b, all natural numbers >= (a-1)(b-1) are linear combinations (with integer coefficients) of a and b.

[1] is this conjecture true?

if so:

[2] what is it called? (couldn't find it online)

[3] are/can the linear combination coefficients be restricted to the natural numbers?

  • 1
    $\begingroup$ Couldn't find it online? Next try a textbook, I guess. $\endgroup$ – Gerald Edgar Jan 31 '13 at 22:36
  • $\begingroup$ Is 3 common in textbooks? (This is an honest question, quite unfamiliar with elementary number theory text books.) $\endgroup$ – user9072 Jan 31 '13 at 23:05
  • $\begingroup$ This is a special case f the postage stamp problem, which states that this is true for every value at least $(a-1)(b-1)$. $\endgroup$ – Alex Becker Feb 1 '13 at 1:19

For 1 and 3, yes. (For 3 assuming both are positive, technically one positive would suffice but then it is essentially reduced to 1, while of course both negative will not work.)

And, note that this is only interisting for natural coefficients, with integers you can write any integer whatsoever, and this is very classical, not even sure how to call this, a direct consequence of Bezout's identity maybe, or an immediate consequence of results on linear diophantine equations.

For 2. The main keyword (with natural coefficients) here is Frobenius problem, but mainly for more than two numbers. Also Coin Problem, Postage Stamp Problem [though it seems some use this to refer to a realted but distinct problem where there is a restrition on the sum of coefficients, on the grounds that an enveloppe can only hold a given number of stamps] or Chicken McNuggets Problem are common more playful names. See http://en.wikipedia.org/wiki/Coin_problem

The solution for 3 is due to Sylvester.

If you have more than two coprime natural numbers $a_1,\dots , a_k$ for integer coefficients you still can write everything. But for natural number coefficients you can only write everythong starting from a certain number $F(a_1,\dots , a_k)+1$ on. To determine the optimal value here is hard (even algorithmically).

This is the Frobenius Problem, and $F(a_1,\dots , a_k)$, the largest number that cannot be written in this form, is called the Frobenius number of $a_1, \dots, a_k$ (or also of the numerical semigroup generated by $a_1, \dots, a_k$ that is just the additive semigroup generated by the $a_i$)

It was in a certain sense solved recently for three numbers by Fel .

There are numerous other contributions on this problem and a lot of literature on numerical semigroups (that appear naturally in other areas of math, see the link above for some info), in particular there is a rather recent (2005) monograph on this subject by J. Ramírez Alfonsín "The Diophantine Frobenius problem."


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.