Skip to content
Skip to navigation menu

The Diophantine Frobenius problem

In the beginning of the 20th century, Ferdinand George Frobenius (1849-1917) raised in his lectures the following problem: given relatively prime positive integers a_1, ..., a_n, find the largest positive integer g=g(a_1, ..., a_n) (called the Frobenius number) that is not representable as a non-negative integer linear combination of a_1, ..., a_n. Nowadays, the question is known as the Diophantine Frobenius problem. There is an explicit formula, traditionally attributed to Silvester, for the Frobenius number of two relatively prime positive integers: g(a_1, a_2)=a_1 a_2 -a_1-a_2. If the number of integers n is three or more, no explicit formula is known. However, for any fixed n, there is an algorithm computing the Frobenius number in polynomial time. The Frobenius problem admits a nice geometric interpretation in terms of covering minima of lattices. For more details we recommend the book of Ramirez Alfonsin (please see the reference below).



  • I. Aliev, M. Henk and A. Hinrichs, Expected Frobenius Numbers,
    J Comb. Theory A, 118 (2011), 525-531.
  • I. Aliev, P. M. Gruber, An Optimal Lower Bound for the Frobenius Problem,
    Journal of Number Theory, 123 (2007), 71-79.
  • J. Marklof, The asymptotic distribution of Frobenius numbers,
    Inventiones Mathematicae, 181 (2010), 179-207.
  • J. Ramirez Alfonsin, The Diophantine Frobenius Problem,
    Oxford University Press, 2005


Back to Number Theory home page