On a Linear Diophantine Problem of Frobenius: Extending the Basis

✍ Scribed by Stefan Matthias Ritter

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 233 KB
• Volume: 69
• Category: Article
• ISSN: 0022-314X
• DOI: 10.1006/jnth.1997.2219

✦ Synopsis

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 representation n= k i=1 x i a i , else independent. The Frobenius number g(X k ) of X k is the greatest integer with no such representation. Selmer 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 give the set C of all independent numbers c satisfying g(A, c)= g(A), where A contains the elements of the arithmetic sequence. Moreover, if a>k then we give as an application, a set B of maximal cardinality such that g(A, B)= g(A) and each element of A _ B is independent of the other ones.