# Frobenius problem

From Encyclopedia of Mathematics

2010 Mathematics Subject Classification: *Primary:* 11D07 [MSN][ZBL]

*coin-change problem*

Given $n$ natural numbers $a_1,\ldots,a_n$ with greatest common divisor $1$, find the largest natural number that is not expressible as a linear non-negative integer combination of the $a_1,\ldots,a_n$.

For $n=2$ the answer is given by $a_1a_2-a_1-a_2$. The general problem is $\mathcal{NP}$-hard.

For a fixed $n$ there is a polynomial-time algorithm to solve the Frobenius problem, [a1].

The Frobenius problem is related to the study of maximal lattice-point-free convex bodies (in the geometry of numbers), [a2].

#### References

[a1] | R. Kannan, "Lattice translates of a polytope and the Frobenius problem" Combinatorica , 12 (1992) pp. 161–172 |

[a2] | L. Lovász, "Geometry of numbers and integer programming" M. Iri (ed.) K. Tanabe (ed.) , Mathematical Programming , Kluwer Acad. Publ. (1989) pp. 177–202 |

**How to Cite This Entry:**

Frobenius problem.

*Encyclopedia of Mathematics.*URL: http://encyclopediaofmath.org/index.php?title=Frobenius_problem&oldid=43102

This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article