ON A LINEAR DIOPHANTINE PROBLEM OF FROBENIUS - EXTENDING THE BASIS

Let X-k = {a(1), a(2),...,a(k)}, k > 1, be a subset of N such that gcd (X-k) = 1. we shall say that a natural number n is dependent (on X-k) if there are nonnegative integers x(i) such that n has a representatio n n = Sigma(i=1)(k) x(i)a(i), else independent. The Frobenius number g (X-k) of X-k is the greatest integer with no such representation. Selm er has raised the problem of extending X-k without changing the value of g. He showed that under certain conditions it is possible to add an element c = a + kd to the arithmetic sequence a, a + d, a + 2d,..., a + (k - 1) d, gcd(a, d) = 1, without altering g. In this paper, we giv e the set C of all independent numbers c satisfying g(A, c)= g(A), whe re A contains the elements of the arithmetic sequence. Moreover, if a > k then we give as an application, a set B of maximal cardinality suc h that g(A, B) = g(A) and each element of A boolean OR B is independen t of the other ones. (C) 1998 Academic Press.