Measuring with Two Jugs

a

5

b

7

c

33

zoom

plot:

x+y0

d

-11

-10

-9

-8

-7

-6

-5

-4

-3

-2

-1

0

1

2

3

4

5

6

7

8

9

10

11

This Demonstration shows a graphic solution of the problem of measuring out

c

liters of a liquid using jugs of capacity

a

and

b

liters, with

a,b,c

integers. The solution seeks the minimal number of times jugs are to be filled and emptied. So we are looking for a solution (in integers) of the Diophantine equation

ax+by=c

with minimal

|x|+|y|

. Another method for solving the equation

ax+by=c

can use two rulers with lengths that are multiples of

a

and

b

. The problem cannot be solved if

gcd(a,b)

does not divide

c

.