Prove that you can make change for any amount greater than 7 cents using only 3 and 5 cent coins. 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$.

 A: 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$.
A: 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.
A: 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.
A: *

*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. :)

A: 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
