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