Every positive integer is the Frobenius number of a numerical semigroup with three generators

Let n1, . . . , np be positive integers with greatest common divisor (gcd for short) one. Then it is not hard to show that there are finitely many nonnegative integers that cannot be expressed as a nonnegative integer linear combination of n1, . . . , np. The largest nonnegative integer fulfilling this condition is usually known as the Frobenius number of n1, . . . , np and it will be denoted throughout this paper by F(n1, . . . , np). The problem of determining F(n1, . . . , np) appears in the literature as the Frobenius coin-exchange problem (for a complete survey on this problem see [5], [6]). For p = 2, Sylvester proved in [7] that F(n1, n2) = n1n2 −n1 −n2. No general formula has been found so far for the case p ≥ 3. Moreover, as Curtis shows in [1], there is no closed formula of a certain type for p = 3. If we focus our attention on this case, then we can think of F as a correspondence that maps three relatively prime integers n1, n2, n3 to a nonnegative integer F(n1, n2, n3). In this paper we prove that this map is surjective, that is, for every positive integer g there exist positive integers n1, n2 and n3 such that F(n1, n2, n3) = g (Theorem 1.11). One easily realizes that every odd positive integer g can be expressed as F(2, g + 2) (see 1.1 (i)). However no even positive integers can be expressed as the Frobenius number associated to a pair of relatively prime numbers. This follows easily from Sylvester’s formula given above, since this formula can be rewritten as F(n1, n2) = (n1 − 1)(n2 − 1) − 1 and n1, n2 are coprime (in fact, it is well known that every numerical semigroup generated by two elements is symmetric, see for instance [2], [4], and thus its Frobenius number must be odd). Thus in order to express any nonnegative integer as the Frobenius number of a sequence of positive integers, the sequences used should be at least of length