Jugs of water puzzle... The problem: 

Explain how to measure 8 units of water using only two jugs, one of
  which holds precisely 12 units, the other holding precisely 17 units of water.

Given the hint "Find $gcd(12,17)$", it is clear that since 17 is prime, $gcd(12,17)=1$. But I am not sure how that actually helps to solve the problem. I don't need a full answer , but just an idea of how to proceed. Anybody have ideas?
 A: First, for any jug problem with jugs of capacities $X$ and $Y$ with $g=\gcd(X,Y)$, you can only end up with quantities of water that are multiples of $g$ after any number of operations (check that every operation you perform conserves the residual respect to $g$). Therefore, the hint has a point of making you realize this connection. In this case you learn that there exists a solution but there's more, which brings me to...
... Second, once you realize this connection, then you know you can write an integer equation $aX+bY=ng$ where one of ${a,b}$ is positive and the other one is non-positive, and $n$ is the desired factor to reach your goal multiple of $g$. I will not solve this equation for your example but I will tell you how to continue once you do. Let's say $a$ is the positive one (since I am not assigning values to $X$ and $Y$, there's no loss of generality), then I can think of $a$ as filling up $X$ and $b$ as emptying $Y$. How do you operate then?
Fill $X$ up, and pour it into $Y$. Every time $Y$ fills up, throw the water away, and continue pouring $X$ into $Y$. After $a$ times you have filled $X$ and poured it into $Y$, and you had thrown the water away $b$ times, then you have $ng$ gallons of water in one of the jugs. Which one will depend on whether you reach $a$ or $b$ first.
This is NOT the most efficient way, but it is what shows the connection between the jugs problems and the $\gcd$. It also lets you know whether it is possible to solve.
A: See Bézout's identity.  This series of equations closely follow a gcd algorithm for 12 and 17.
$$\begin{align}
\text{(1)}&& 17a - 12b = 8
\\ \text{(2)} && \text{Let } c = b - a
\\ \text{(3)} && 5a - 12c = 8
\\ \text{(4)} && \text{Let } d = a - 2c
\\ \text{(5)} && 5d - 2c = 8
\\ \text{(6)} && \text{Let } e = c - 2d
\\ \text{(7)} && d - 2e = 8, \text{ so } d = 8 + 2e
\\ \text{(8), from (6) and (7)} && c = 16 + 5e
\\ \text{(9), from (4), (7), (8)}&& a = (8+2e) + 2(16+5e) = 40 + 12e
\\ \text{(10), from (2), (8), (9)}&& b = (16+5e) + (40 + 12e) = 56 + 17e
\end{align}
$$
Set $e = -3$ and you get $a = 4, b = 5$.  Fill the 17-jug 4 times and empty the 12-jug 5 times and you get $4\cdot17 - 12\cdot5 = 68 - 60 = 8$ units.
