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).
 |
References
|