From: kovarik@mcmail.cis.McMaster.CA (Zdislav V. Kovarik)
Newsgroups: sci.math
Subject: Re: easier question-pls help
Date: 26 Oct 1998 12:06:21 -0500

In article <Pine.GSO.3.95qL.981025111019.4387A-100000@sawasdee.cc.columbia.edu>,
greg  <ref15@sawasdee.cc.columbia.edu> wrote:
:Could someone give some ideas on how to prove the following:
:(this is not a homework problem, but I think I can use it to solve a
:certain homework problem as a subsidiary step).
:Given two integers, a and b, where gcd(a, b) =1.
:Any integer  n above a certain value (? it might be all integers > ab-1)
:can be represented, not necessarily uniquely, as: n = ax + by, where x
:and
:y are integers.  (E.g. 23 = 3*1 + 5*4.)
:How can this be proved? 
:thanks

I've seen it as "Sylvester's Theorem":

For integers a>=1, b>=1, and gcd(a,b)=1 , the largest integer S _not_
obtainable as  a*x+b*y with x, y >=0 integers, is

     S = a*b - a - b.

The proof, if you are interested only in an upper estimate of S, goes like
this:

There are non-negative integers p, q such that a*p - b*q = 1, and
non-negative integers P and Q such that -a*P + b*Q = 1 (a well-known
property of gcd).

If you want to proceed form  a*x + b*y = C to a*X + b*Y = C+1 (to show
what you want), you can go by

    a*(x+p) + b*(y-q) = C+1

or by

    a*(x-P) + b*(y+Q) = C+1

provided that  either x>=P or y>=q, or both. This will fail for

   x<=P-1 and y<=q-1.

For these borderline values, you get

  a*x + b*y <= a*(P-1) + b*(q-1).

So, if C >= a*(P-1) + b*(q+1) + 1, then the induction trick will work.

If you want to get the minimal C,  you have to be more careful about how
p, q, P, Q are chosen.

Good luck, ZVK(Slavek).