Measure exactly $n$ gallons of water using 9- and 15- gallon jugs...

Question

In order to disarm a bomb, Samuel L. Jackson and Bruce Willis must measure exactly $n$ gallons of water using a 9-gallon jug and a 15-gallon jug. Select the values of $n$ for which this is possible.

(a) $n = 3$
(b) $n = 5$
(c) $n = 7$
(d) $n = 12$

What I did was try and find $\gcd(15,9)$ which I found to be 3. So would 3 be the answer?

Answer 1

We seek solutions to to $$ 9x+15y=n $$ where $x$ and $y$ are integers (necesarily at least one of $x$ or $y$ must be positive). Observe that a necessary condition is that $3|n$. Hence (b) and (c) are not possible. The condition $3|n$ is also sufficient by bezout's lemma. Since the gcd of $15$ and $9$ is $3$, by Bezout's lemma, we can find integers $a,b$ such that $$ 9a+15b=3 $$ for example $$ 9(2)+15(-1)=3 $$ and so $$ 9(8)+15(-4)=12 $$ The answer is (a) and (d).

Answer 2

The question asked for all possible answers. In this case, $\gcd(9,15)=3$ and the nature of the problem means that (a) or $n=3$ is an answer, but all multiples of 3 are achievable. Thus (d) or $n=12$ is the other answer.