If $a, b$ are positive and coprime integers, then the set of linear combinations of $a$ and $b$ with nonnegative coefficients is all integers past $(a - 1)(b - 1)$; i.e. $\{ \lambda_1 a + \lambda_2 b : \lambda_1, \lambda_2 \in \mathbb{Z}_{\geq 0} \} = (a - 1)(b - 1) + \mathbb{Z}_{\geq 0}$.

On Wikipedia (https://en.wikipedia.org/wiki/Coin_problem), it says "This formula was discovered by James Joseph Sylvester in 1882,[6] although the original source is sometimes incorrectly cited as,[7] in which the author put his theorem as a recreational problem[8] (and did not explicitly state the formula for the Frobenius number)."

Citation [6] is: Sylvester, J. J. (1882). On subvariants, ie semi-invariants to binary quantics of an unlimited order. American Journal of Mathematics, 5(1), 79-136.

Citation [7] is: Sylvester, J. J. (1884). Question 7382. Mathematical questions from the educational times, 37, 26.

Citation [8] is: Alfonsín, J. L. R., & Alfonsín, J. L. R. (2005). The diophantine Frobenius problem. Oxford University Press.

  1. Where in Sylvester's paper does he prove this formula? I tried finding it but had no luck.
  2. Did Frobenius have anything to do with this proof? These types of problems are called "Frobenius problems," so it's a little strange that Sylvester is the pioneer.
  3. Did anyone famous other than Sylvester independently discover their own proof of this formula? It seems that W. J. Curran Sharp responded to Sylvester's recreational problem in the Educational Times. In other words, should Sylvester get all the credit?
  4. What is a timeline for the first results on the Frobenius problem?

The preface of [8] says that Frobenius brought up these problems in his lectures. [8] also says that Sylvester proved in 1882 that the number of positive integers that are not expressible as nonnegative linear combinations of $a, b$ is $\frac{1}{2}(a - 1)(b - 1)$. Then [8] mentions citation [7]: "in 1884, in the Educational Times journal, Sylvester posed (as a recreational problem) the question of finding such a formula." The book [8] has citations, but unfortunately I only have online access to the preface.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.