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(adsbygoogle = window.adsbygoogle || []).push({});

-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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

**Physics Forums | Science Articles, Homework Help, Discussion**