From: Pierre Bornsztein <pbornszt@club-internet.fr>
Subject: Re: Linear Combination of Non-negative integers.
Date: Tue, 22 Aug 2000 11:06:30 +0200
Newsgroups: sci.math.research
Summary: [missing]

Darren Narayan wrote:
> 
> Here is a question whose likes appear on problem solving competitions.
> 
> Let a and b be distinct positive integers where gcd(a,b)=1. Determine
> the largest integer, N that CANNOT be expressed as a linear
> combination N = xa + yb where x and y are also non-negative integers.
> 
> It is known that N equals ab - a - b, which can be easily proved.
> 
> However does anyone know who originally proved this? One suggestion
> was Schur but I have not verified this yet.
> 
> D. Narayan
> RIT
> 
> 

Hi,

according to Guy's "unsolved problems in number theory" Springer p.113
(C7), this result is due to Sylvester (1884), who also proved that the
number of non-representable numbers is (a-1)(b-1)/2.
The general problem with n > 1 numbers is known as the coin exchange
problem of Frobenius.
The case n = 3 has been solved by Selmer and Beyer, then simplified by
Rödseth and later by Greenberg. But there is no formula as simple as
above.
For n > 3, only bounds are known.

Pierre.