Relatively prime property verification

I am reading a computer science puzzles book.

And I get the following question -

"You have a five quart jug, a three quart jug and unlimited supply of water. How would you come up with exactly four quarts of water ?"

The question is pretty simple and I figured the sequence of "water transfers" to solve it.

But there was an interesting side-note that I did not know.

The side-note said that as long as the two jugs size relatively prime, it is possible to find a pour sequence for any value between one and the sum of the jug sizes.

It is true for 5 and 3.

But I want to know if it is really generally true or not ? If it is, it is really cool! What is the theorem called ? Who discovered it ?

Let two wine glasses A and B have capacities $a$ and $b$ ounces, where $a$ and $b$ are relatively prime positive integers, and $a\lt b$. Suppose we also have a large open barrel full of wine. We will show that for any integer $w$, where $0\le w\le b$, we can measure out $w$ ounces of wine. (This means that we can measure out any integer number $y\le a+b$ of wine ounces, as long as we don't mind the stuff being possibly in two glasses. I don't.)

It is enough to show that for any $r$, with $0\le r\lt a$, we can measure out $r$ ounces. For $w=qa+r$ for some $r$ between $0$ and $a-1$. So if we can measure out $r$ ounces, we can put this into B, and then get to $w$ by using glass A $q$ times.

The construction goes as follows. Suppose that at a certain stage we have $x_k$ ounces of wine in cup A. Fill cup B from the barrel, top up cup A from cup B, pour the contents of A into the barrel, or better, drink it. Keep on filling A from cup B, dumping the contents of A into the barrel when A gets full. After a while, the amount left in B will be insufficient to fill A, but pour it in anyway. Call the amount that is now in A by the name $x_{k+1}$. Then $$b=(a-x_k)+an+x_{k+1}$$ for some integer $n$. It follows that $$x_{k+1}\equiv x_k +b\pmod{a}.$$ Start with A empty, that is, with $x_0=0$. Then $x_1\equiv b\pmod{a}$, $x_2\equiv 2b\pmod{a}$, and so on.

But since $a$ and $b$ are relatively prime, the numbers $0,b,2b.3b,\dots, (a-1)b$ form a complete residue system modulo $a$. Thus the sequence $x_0,x_1,x_2,\dots,x_{a-1}$ runs, in some order, through all the numbers from $0$ to $a-1$. This completes the proof.

Yes, it is true. From Diophantine Equations on Wikipedia

The simplest linear Diophantine equation takes the form ax + by = c, where a, b and c are given integers. The solutions are completely described by the following theorem: This Diophantine equation has a solution (where x and y are integers) if and only if c is a multiple of the greatest common divisor of a and b. Moreover, if (x, y) is a solution, then the other solutions have the form (x + kv, y - ku), where k is an arbitrary integer, and u and v are the quotients of a and b (respectively) by the greatest common divisor of a and b.

Look at the Wikipedia article for more details of a proof.

To try to connect things, consider the equation: 5x+3y=4 as x could represent the number of filling or emptying of the 5 quart jug while y represents the same thing for the 3 quart jug. If there was a common factor between these, this could be factored out so that any answer would be a multiple of that integer. Given that a solution is (2,-2) to that Diophantine equation, this could imply that one fills the 5 quart jug and empties it over the 3 quart jug a couple of times to get exactly 4 quarts assuming one has another container to hold the 4 quarts.

I'll admit that I've seen this problem from Die Hard 3, so I know of an alternate solution.

Consider the case where there is a common factor between the jug sizes where one has jugs of size 8 and 12. Now, the greatest common divisor of 8 and 12 is 4 and thus any combination of pourings will leave you with a multiple of 4 for an answer as 8x+12y=4(2x+3y) and thus while one can easily solve 2x+3y=1, it is a bit different to solve 4(2x+3y)=1 where x and y are integer values as no solutions exist here.

In contrast, consider that if for a given pair of jug sizes that one can get exactly 1 of the unit then this could be repeated for any Natural number greater than 1 so to get any other value is rather easy if you can get 1.

The first part of my answer covers this in a general case, but for the sake of argument let's take $5x+3y=z$. If $z=1$ then by inspection I can notice that x=-1,y=2 is a solution. There are many solutions as one could take that solution and make the parametrized solution of $x=-1+k,y=2-k$ for k being any integer. Now, if z is some other value, I could just multiply the initial solution to get that value. Thus, if $z=4$ then $x=-4,y=8$ is a solution which works as $5*(-4)+3*8=-20+24=4$.

This last part is fairly trivial to my mind if you remember that one can take an equation and multiply both sides by a non-zero value and maintain equality.