ON THE LINEAR DIOPHANTINE PROBLEM OF FROBENIUS

Suppose a, b, c are three positive integers with gcd = 1. We consider the function f(a, b, c) defined to be the largest integer not representable as a positive integral linear combination of a, b, c. We give a new lower bound for f(a, b, c) which is shown to be tight, and we give a new proof of a theorem due to Vitek on an upper bound. A polynomial time algorithm, based on modifications to Rodseth and Selmer/Beyer algorithms, is given for the computation of f(a, b, c). Finally, some open problems are discussed. (C) 1994 Academic Press, Inc.