The Postage Stamp Problem Using Money and seeing if possible without change Here is the problem:

Suppose you have only 13-dollar and 7-dollar bills.
a) You need to pay someone 71 dollars. Is this possible without receiving change? If so, show how to do it. If not, explain why it is impossible.
b) Suppose you need to pay someone 75 dollars. Is it possible? If so, show how to do it. If not, explain why it is impossible.

I have been trying to do this problem but I get stuck after I write the equation $13x+7y=71$. I know that the $\gcd(13,7)=1$ and $1$ divides $71$, so there must be infinite solutions, but I don't know how to actually solve the equation and limit the answer to no change.
 A: A few things to note:
1) There are integer solutions to $Kx + My = Z$ if and only $\gcd(K,M) | Z$.  BUT these solutions might have negative integer values.
$\gcd(13,7) = 1$ and $1$ divides everything so a) and b) have solutions but they may b be negative solutions which are not acceptable for monetary transactions.
2) To determine possible solutions for $Kx + My = Z = Z'\gcd(K,M)$:
It suffices the assume $\gcd(M,) = 1$ as $Kx + My = Z'\gcd(K,M)$ will have the exact same  solutions as $\frac {K}{\gcd(K,M)}x + \frac{M}{\gcd(K,M)} = Z'$.
It also suffices to assume $K \not \mid Z$ so as $K\frac{Z}K + M*0 = Z$ would be a trivial and obvious solution.
So we will assume if $Kx + My = Z$ then $x \ne 0$ and $y \ne 0$.
If $Kx + My = Z$ is a solution so is $K(x \pm Mj) + M(y \mp Kj) = Z$.
If $Kx + My =Z$ and $Kx' + My' = Z$ are two solutions then $Kx = Z - My$ so $My \equiv Z \mod K$. Likewise $My' \equiv Z \equiv My \mod K$.  As $\gcd(M,K) = 1$ it follows $y \equiv y' \mod K$.
And obviously we can do the same for $x$.  $x \equiv x' \mod M$ for the exact same reasons.
So $K(x \pm Mj) + M(y \mp Kj) = Z$ are the only solutions and we can find these solutions by solving $My \equiv Z \mod K$ and $Kx \equiv Z \mod M$.
So for example:
a) $7a + 13b = 71$ will have solution when $13b \equiv 71 \mod 7$ so $-b \equiv 1 \mod 7$ so $b \equiv -1 \mod 7$. So $b = -1$ and $7a -13 = 71 \implies a=12$ will be a solution.
$7*12 + 13(-1) = 71$ is a solution.  But it is not an acceptable non-negative solution.
b) $7a + 13b = 75$ will have a solution when $13b \equiv 75 \mod7$ so $-b \equiv 5 \mod 7$ so $b \equiv -5 \mod 7$.   So $b = -5$ and $7a - 13*5 = 75 \implies $a = 20$ will be a solution.
$20*7 - 5*13 = 75$ is a solution but not positive.
3) Finding positive solutions (if any).  
If $K(u+Mj) + M(w- Kj) = Z$ are sets of solutions.  $u + Mj \ge 0$ if $j \ge -u/M$.  $w - Kj \ge 0$ if $j \le w/K$.  If there exists $-u/M \le j \le w/K$ then there will be all positive solutions for each possible $j$.  Otherwise there will not be.
So for a)
$7*12 - 13*1 = 71$. We want $7(12 - 13j) + 13(-1 + 7j)= 71$ and we want $1/7 \le j \le 12/13$.  There are no such $j$ and so no positive solutions.
So for b)
We want $7(20 - 13k) + 13(-5 + 7k) = 71$.  So we want $5/7 \le k \le 20/13$.  There is exactly one such $k$ ($k = 1$) so the only positive solution is:
$7(20 - 13) + 13(-5 + 7) = 7*7 + 13*2 = 71$.
A: a)
You have $71 = 10\cdot 7 + 1 \equiv 1 \pmod 7$ so if you try to pay $71$ with $7$-s you'll end up with $1$ to pay. Let's see if $13$-s help.
$13 = 7+6 = 2\cdot 7-1 \equiv 6 \equiv -1 \pmod 7$, so you would need to pay $6$ times $13$ to get a remainder of $1$:
$$6\cdot 13 = 78 = 11\cdot 7+1 \equiv 1 \pmod 7$$
– but that exceeds the value to be paid. You can't pay $71$ with bills of $7$ and $13$ only.
b)
OTOH $75 = 11\cdot 7 - 2 \equiv -2 \pmod 7$, so $2\cdot 13$ should suffice. Let's check:
$2\cdot 13=26$ and $75-26 = 49 = 7\cdot 7$ — yes, you can pay $75$ with seven bills of $7$ and two of $13$.
A: Suppose either $71$ or $75$ can be made up with $n$ bills, in some combination of $7$ and $13$.  Then $6 \leq n \leq 10$ (since $5\times13=65 < 71$ and $11\times7=77 > 75$). 
Since $7=(1\times6)+1$ and $13=(2\times6)+1$, we must have, for some integer $m$:
$$\text{Sum of n bills} = 6m+n$$
a) Then we require $71=6m+n$ with $6\leq n\leq10$, which implies $61\leq6m\leq65$. But this is impossible, so $71$ cannot be made up.
b) We require $75=6m+n$ with $6\leq n\leq10$, which implies $65\leq 6m\leq69$ and is solved by $m=11$ and $n=9$. Hence $75$ can be made up using 2 13-dollar bills (because $m-n=11-9=2$ and therefore 7 7-dollar bills.
