Give change for any amount greater than $ab-a-b using only $a,$b w/ gcd(a,b)=1

[wendylg]

One day a group of my friends and I were playing around with some Math questions in school and we made an observation that if you are given $a notes and $b notes only, and the greatest common divisor of a and b is 1 (ie a,b are relatively prime), then
-you cannot give change for $ab-a-b,
-but you can for every amount greater than $ab-a-b.
How can this be proven? Please see if the idea of using an induction proof would work and if yes, how it can work.

We were thinking about proving it by induction on the amount of money to give change for. This seems to be the best way to prove a statement that is true for every amount greater than something. First we should prove that there is no way to express ab-a-b as ak+bl where k,l are natural numbers including 0 (i.e. cannot give change for $ab-a-b), and then for the induction proof, the base case would be to prove that you can express ab-a-b+1 as ak+bl.

I am not sure how to incorporate the factor that a,b are relatively prime (which seems to be an important factor) into the proof since it is hard to represent it in a single expression. It does not really suggest what a and b each are restricted to be but rather restrctions are relative between a and b. This is especially hard when there are no specified numbers in the problem. ab-a-b= either a(b-1)-b or b(a-1)-a. How can these be eventually expressed (or show that it cannot be expressed) as ak+bl (k $a notes and l $b notes)?

Thank you very much for your attention.

 

[CarlB]

If ab-a-b = aj + bk, then ab = a(j+1) + b(k+1). Divide both sides by b. You get: a = a(j+1)/b + (k+1). Thus b divides j+1, or j+1 = mb and m is a positive integer or zero. Similarly, k+1 = na with n a positive integer or zero. Now you have ab = amb+bna or 1 = m+n. From here you should be able to get a contradiction.

Carl

 

[ivybond]

http://www.csulb.edu/~acaproj/Spring98/uchida.html

 

[wendylg]

Why does b divide j+1?

If ab-a-b = aj + bk, then ab = a(j+1) + b(k+1). Divide both sides by b. You get: a = a(j+1)/b + (k+1). Thus b divides j+1, or j+1 = mb and m is a positive integer or zero. Similarly, k+1 = na with n a positive integer or zero. Now you have ab = amb+bna or 1 = m+n. From here you should be able to get a contradiction.
Carl

Thanks very much for your help Carl, but I do not understand how you can conclude "b divides j+1". Could you please explain? Thanks very much again.

 

[CarlB]

Thanks very much for your help Carl, but I do not understand how you can conclude "b divides j+1". Could you please explain? Thanks very much again.

a = a(j+1)/b + (k+1) so

a(j+1)/b = a-(k+a).

The right hand side is an integer, and so is the left hand side. Every prime power in b, for example, p^m, must be contained in a(j+1). But a and b have GCD(a,b)=1, so they have no common prime factors. Thus p^m must divide (j+1). This is true for all the prime powers in b, so b must divide (j+1).

Carl