# Diophantine equation word problem

A piggy bank contains $24$ coins, all of which are nickels, dimes, or quarters. If the total value of the coins is two dollars, what combination of coins are possible?

So far I have: $n$=# of nickels, $d$=# of dimes, $q$=# of quarters

$n+d+q=24$

$5n+10d+25q=200$

$q=24-n-d$

thus: $5n+10d+25(24-n-d)=200$ $-20n-15d=-400$

Next I would find the gcd using long division but I was wondering how I go about this since all the numbers are negative.

Does this affect the problem or not?

• The gcd also makes sense for negative numbers, so it should not affect the problem. – Peter Mar 23 '14 at 15:28

## 1 Answer

Consider your two equations $$n+d+q=24$$ $$5n+10d+25q=200$$ Since the number of quarters will probably be the smallest, extract $n$ and $d$ as a function of $q$ solving the two linear equations $$n+d=24-q$$ $$5n+10d=200-25q$$

You arrive to $n=8+3q$ and $d=16-4q$ and you know that $q$ must be positive or zero and smaller or equal to $8$ (if only quarters, $2$ dollars will be made by $8$ quarters). However, the number of dimes cannot be negative; this then implies that $0 \leq q \leq 4$.

I am sure that you can take from here.