Prove that you can make change for any amount greater than 7 cents using only 3 and 5 cent coins.

Question

I am pretty sure this question has something to do with the Least Common Multiple.

• I was thinking that the proof was that every number either is or isn't a multiple of $3, 5$, and $8\left(3 + 5\right)$.
• If it isn't a multiple of $3,5$, or $8$, great. You have nothing to prove.
• But if it is divisible by one of them, I couldn't find a general proof that showed that it wouldn't be divisible by another one. Say $15$, it is divisible by $3$ and $5$, but not $8$.

Answer 1

It has been shown that if you have two coins of values $a $ and $b$, then you can make any value greater than $ab - a - b $ with them. For your case, this yields $7$.

As suggested in the comments, for you it suffices to show you can make $8$, $9$ and $10$ cents explicitly. Then any other number will be a given amount of $3$ cent coins plus $8, 9$ or $10$.

The way it works is: let $n > 7$. Then either $n $ is a multiple of 3, a multiple of 3 plus one, or a multiple of 3 plus 2. Hence $n = 3k + (0,1,2) $ for some $k $.

Notice that $8 = 2\cdot3 + 2$, $9 = 3\cdot3$ and $10 = 3\cdot3 + 1$.

If $n $ is $3k$, then just flat out add $k $ coins of 3 cents. If $n = 3k + 1$, then $n - 10 = 3(k - 3)$ thus you add $k-3$ coins of three cents to the 2 coins of 5 cents that make up 10. That is $2\cdot5 + (k-3)3 = 10 + 3k - 9 = 3k + 1 = n $. Analogously if $n = 3k + 2$, we use $8$.

Answer 2

If we have $a,b$ let $\gcd(a,b)=d$ and $a=da',b=db'$. Then $\operatorname{lcm}(a,b,a+b)=d\cdot\operatorname{lcm}(a',b',a'+b')$.

And $\gcd(a,a+b)=\gcd(b,a+b)=d$.

So $a,b,a+b|n$ if and only if $\operatorname{lcm}(a,b,a+b)|n$.

The LCM of $3,5,8$ is $120$, so $n$ must be a multiple of $120$ in your example.

Answer 3

A formal induction: Any integer $k>7$ can be expressed as $3a+5b = k$, with $a,b\ge 0$.

Base cases:

• $k=8 \implies a=1,b=1$
• $k=9 \implies a=3,b=0$
• $k=10 \implies a=0,b=2$

Induction:

Assume that the statement holds for all $k<m$, and $m>10$. In particular since $m-3>7$, then statement holds for $n := m-3$. Now set $a_m = a_n +1, b_m = b_n$ and:

$$3 a_m + 5b_m = 3 (a_n+1) + 5b_n = 3+ 3a_n + 5b_n = 3+n = m$$

Showing that the statement also holds for $m$ and the induction is complete.

Answer 4

• proof by strong induction for n,a,b.
• proof hypotheses p(n) = 3*a + 5*b for all n >= 8 //any number greater than 7 consists of 3s and 5s.
• base case p(8) holds because it consists of 3 and 5.
• Inductive step: we assume p(n) holds for all n>=8 we must prove that p(n+1) holds:
  since p(n+1) = k+m
  since k,m<=n then p(k),p(m) holds for some 3*a + 5*b
  then p(n+1) = 3*a + 5*b + 3*a + 5*b
  we conclude that we can make change for any number greater than 7.
  I suppose & hope this works. :)

Answer 5

proof by induction

p(8): 3.(1)+5.(1)=8 holds

Assume p(k) holds => 3.a + 5.b = k

we must prove that p(k+1) holds.

p(k+1): 3x+5y = k+1=> 3x+5y = 3a+5b+1=> 3(x-a) + 5(y-a)

thus suffices to prove that 3z+5ω =1 has an integer solution. That is true because gcd(3,5)=1 | 1 (1 devdes 1)

Calculating gcd(3,5) gives: 5 = 1*3 + 2

3 = 1*2 + 1

2 = 2*1 + 0

Then applying the Extended Euclidean Algorithm:

1 = (1 * 3) + (-1 * 2) = (-1 * 5) + (2 * 3)=> z0=2, ω0=-1 => 3.2+5.(-1) = 1=> p(k+1) holds as well