Measure exactly $n$ gallons of water using 9- and 15- gallon jugs... 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?

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