Do there exist infinite such triplets ?

[Vikraman Choudhury]

For all natural numbers n >= 2, n can be expressed as 2a + 3b, where, a,b >= 0.
Similarly, for n >= 5, n can be expressed as 2a + 5b, where, a,b >= 0.
Again, for n >= 8, n can be expressed as 3a + 5b, where, a,b >= 0.

I can prove these easily.

My question is, do there exist infinite such triplets (a,b,c), such that any natural number n >= c can be expressed as n = ax + by, where, x,y >= 0 ?

I tried playing around with some co-prime values for a and b, with c = a + b, but it failed easily! Maybe there is a higher value of c for which the claim is true ?

[Dibyendu Das]

for your 3rd case n should be >= 5, such that n can be expressed as 3a + 5b, where, a,b >= 0.

[Vikraman Choudhury]

Nope, n = 7 isn't 3a + 5b!

[Butch Malahide]

On Feb 9, 2:00 pm, Vikraman Choudhury <vikraman.choudh...@gmail.com>
wrote:

For coprime natural numbers a and b, it holds for all c >= (a - 1)(b -
1), while it fails for c = ab - a - b. This is a theorem of Sylvester,
and solves the Frobenius coin problem for the case of two coins.

https://en.wikipedia.org/wiki/Coin_problem

[Vikraman Choudhury]

Thank you, that completely solves the problem. The proof is also very interesting.

I wrote O(n^2) code to find c given a,b, and now I feel so dumb! :-/

[Butch Malahide]

On Feb 9, 2:53 pm, Butch Malahide <fred.gal...@gmail.com> wrote:
> On Feb 9, 2:00 pm, Vikraman Choudhury <vikraman.choudh...@gmail.com>
> wrote:

> > [. . .]

> > My question is, do there exist infinite such triplets (a,b,c), such that any natural number n >= c can be expressed as n = ax + by, where, x,y >= 0 ?
>
> > I tried playing around with some co-prime values for a and b, with c = a + b, but it failed easily! Maybe there is a higher value of c for which the claim is true ?
>
> For coprime natural numbers a and b, it holds for all c >= (a - 1)(b -
> 1), while it fails for c = ab - a - b. This is a theorem of Sylvester,
> and solves the Frobenius coin problem for the case of two coins.
>
> https://en.wikipedia.org/wiki/Coin_problem

Here is a proof.

Consider coprime positive integers a,b and an integer
n > ab - a - b; we want nonnegative integers x,y such
that ax + by = n. Equivalently (substitute x = u - 1,
y = v - 1), we want positive integers u,v such that au + bv = m
where m = n + a + b > ab.

First, find integers r,s such that ar + bs = t. Then,
setting u = mr + bt, v = ms - at will satisfy au + bv = m.
Thus, we need only find an integer t such that
mr + bt > 0 and ms - at > 0, i.e., -mr/b < t < ms/a.
But there must be at least one integer in the interval (-mr/b, ms/a),
since the length of the interval is ms/a + mr/b = m/ab > 1.

[Butch Malahide]

On Feb 9, 4:10 pm, Butch Malahide <fred.gal...@gmail.com> wrote:
> On Feb 9, 2:53 pm, Butch Malahide <fred.gal...@gmail.com> wrote:
>
> > On Feb 9, 2:00 pm, Vikraman Choudhury <vikraman.choudh...@gmail.com>
> > wrote:
> > > [. . .]
> > > My question is, do there exist infinite such triplets (a,b,c), such that any natural number n >= c can be expressed as n = ax + by, where, x,y >= 0 ?
>
> > > I tried playing around with some co-prime values for a and b, with c = a + b, but it failed easily! Maybe there is a higher value of c for which the claim is true ?
>
> > For coprime natural numbers a and b, it holds for all c >= (a - 1)(b -
> > 1), while it fails for c = ab - a - b. This is a theorem of Sylvester,
> > and solves the Frobenius coin problem for the case of two coins.
>
> >https://en.wikipedia.org/wiki/Coin_problem
>
> Here is a proof.
>
> Consider coprime positive integers a,b and an integer
> n > ab - a - b; we want nonnegative integers x,y such
> that ax + by = n. Equivalently (substitute x = u - 1,
> y = v - 1), we want positive integers u,v such that au + bv = m
> where m = n + a + b > ab.
>

> First, find integers r,s such that ar + bs = 1. Then,

> setting u = mr + bt, v = ms - at will satisfy au + bv = m.
> Thus, we need only find an integer t such that
> mr + bt > 0 and ms - at > 0, i.e., -mr/b < t < ms/a.
> But there must be at least one integer in the interval (-mr/b, ms/a),
> since the length of the interval is ms/a + mr/b = m/ab > 1.

I corrected a typo in the above proof, which you don't need since you
already found the proof somewhere else, but maybe some lurker is
interested.

[bill]

On Feb 9, 12:00 pm, Vikraman Choudhury <vikraman.choudh...@gmail.com>
wrote:

What is wrong with a = 1, 1 <= b < oo, c = b +2?

regards,

Bill J

[Butch Malahide]

Nothing. The question in the sentence beginning "My question is" is
quite silly, and it is hard to believe that that was what the OP
really meant to ask. At any rate, I ignored it and answered the
question implicit in the rest of the message, and the OP seemed to be
satisfied with that.

[Vikraman Choudhury]

Oh right, I really meant non-trivial values. I guess I framed my question wrong!