# Given $r$ and $s$ litre jugs, $m$ litres of water can be measured for any positive integer $m$

The problem is:

Show that it is possible to measure any integral number of litres using only a $3$ litre and a $7$ litre jug.

And then the book says it's true that given $r$ and $s$ litre jugs, $m$ litres of water can be measured for any positive integer $m$. It's seems trivially true but I don't know how to "show" it. Doesn't it hold on the condition that $(r,s)=1$?

-
Yes. the condition on $\gcd$ is necessary. Say, if $r$ and $s$ are both even, you will never get an odd number to come out. Proof? Bezout's identity? – Jyrki Lahtonen Jul 8 '12 at 8:28
@JyrkiLahtonen: Umm, so I should use Bezout's identity to show that? – Gigili Jul 8 '12 at 9:43
Bezout's identity shows that you can get 1 liter. The rest is easy. – Jyrki Lahtonen Jul 8 '12 at 10:16

We put stringent conditions on the equipment we have, and show that we can still do it. We have two jugs, $A$ and $B$, a large barrel full of water, and no other container. (An additional container makes the problem too easy, for then we only need to know how to do $1$ litre.)

Jug $A$ can hold $a$ litres of water, and jug $B$ can hold $b$ litres, where $a$ and $b$ are relatively prime integers, and $a \lt b$. We show that for any non-negative integer $x\le b$, we can end up with $x$ litres of water in jug $B$.

The main problem is to show that for any positive integer $r\lt a$, we can end up with $r$ litres in jug $A$. For $x=qa+r$ for some non-negative quotient $q$ and remainder $r$ where $0\le r\lt a$. If we can achieve $r$ in jug $A$, we can achieve $x$ in $B$ by pouring the contents of $A$ into the emptied jug $B$, and adding $q$ jugfuls from $A$.

We now proceed to the construction of any desired $r$ in jug $A$, by providing an explicit algorithm.

Let $r_0=0$. Suppose that at a certain Stage $k$, we have $r_k$ litres of water in jug $A$. Fill $B$ from the barrel, top up $A$ from $B$, pour the contents of $A$ back into the barrel. If there is water left in $B$, keep filling $A$ from $B$, and emptying $A$ into the barrel whenever $A$ is full.

After a while, the amount that remains in $B$ is not enough to fill $A$. Put it into $A$ anyway. Call the amount we now have in $A$ by the name $r_{k+1}$, the amount at Stage $k+1$.

Then $b=(a-r_k)+an+r_{k+1}$ for some integer $n$. In congruence notation, we have $r_{k+1}\equiv r_k+b \pmod{a}$. Since $r_0=0$, we have $r_1\equiv b\pmod{a}$, $r_2\equiv 2b\pmod a$, and in general $$r_k\equiv kb\pmod{a}.$$

Since $a$ and $b$ are relatively prime, the set $\{0,b,2b,3b,\dots, (a-1)b\}$ is a complete residue system modulo $a$. Thus the sequence $r_0,r_1,\dots, r_{a-1}$ runs, in some order, through the numbers $0,1,2,\dots, a-1$. It follows that for any $r$ with $0 \le r \lt a$, there is a $k$ such that at Stage $k$ we have $r$ litres in jug $A$.

Note that the $k$ for which we have $r_k=r$ at Stage $k$ is obtained by solving the congruence $kb\equiv r\pmod{a}$. That provides the stopping rule for the algorithm.

Suppose that $d=\gcd(a,b)$, and let $x\le b$ be any non-negative integer multiple of $d$. A minor modification of the argument shows that we can end up with $x$ in $B$.

-
The problem was for any positive integer $m$. – copper.hat Jul 8 '12 at 20:02

I'm not exactly sure what you are asking, but if you fill the 7 litre jug and then fill the 3 litre jug from the 7 litre jug twice (emptying in between, of course), you will be left with 1 litre in the 7 litre jug.

This allows you to measure out 1 litre. For n litres, repeat the process n times.

This, of course, comes from the fact that $1 \cdot 7-2 \cdot 3 = 1$.

-
That's not what I am asking, I already knew that. It's a high school level maths. – Gigili Jul 8 '12 at 9:30
If $\gcd(r,s)=1$, then the Bezout identity shows the existence of $a,b$ such that $a r + b s = 1$. Suppose $a>0$, then fill up another container with the $r$ jug $a$ times. Then remove the $s$ jug $b$ times. This will leave $1$ litre. Repeat the process $m$ times. Explicit enough for you? – copper.hat Jul 8 '12 at 9:46
And there is no need to get snippy. In my day the Euclidean algorithm was considered high school maths. So what was it you were asking? – copper.hat Jul 8 '12 at 9:48
My question is what I posted above. You comment answers the question much better than your answer. And yes, there is no need to get snippy. – Gigili Jul 8 '12 at 10:03
Thank you for your answer! – Gigili Jul 8 '12 at 10:08