A Remark Related to the Frobenius Problem

Abstract

The Frobenius problem [2; 3] is to find, for a given set al3..., am of relatively prime integers, the largest number which is not a linear combination of au...,am with nonnegative integer coefficients. Given a set a1?...,aw of relatively prime positive integers, let us agree to call a number representable if it is a linear combination of au...,am with nonnegative integer coefficients; otherwise, we call it nonrepresentable. The fact that every sufficiently large positive integer is representable (given relatively prime a a \\, • ••, m) has been rediscovered many times, and makes a good exercise in a course in elementary number theory. The Frobenius problem has a long history. (See [7] for a list of references.) In 1884, J. J. Sylvester [8] completely solved the problem for m = 2. He found that if a and b are positive integers such that (a, b) = 1, then every n>(a- l)(b-1) can be expressed in the form n = xa~hby where x, y are nonnegative integers, and ab-a-b cannot be so expressed. That is, the largest nonrepresentable number in this case is ab-a-b. Sylvester also found that among the