completely filled twice and the 3-gallon jug completely

emptied three times.) Since 1 is the

GREATEST COM

-

MON FACTOR

of 3 and 5, the E

UCLIDEAN ALGORITHM

provides solutions to the equation x × 3 + y × 5 = 1,

and hence to the jug-filling problem.

As a variation we ask: is it possible to obtain

exactly 1 gallon of water using a 9-gallon jug and a 15-

gallon jug? This would require finding a solution to the

equation x × 9 + y × 15 = 1. If there were a solution to

this problem, then 1 would be a combination of two

multiples of 3, and so itself a multiple of 3. This, of

course, is absurd, and there is no solution to this prob-

lem. This type of argument can be used to show that d

gallons of water can be obtained from an a-gallon jug

and a b-gallon jug if, and only if, dis a multiple of the

greatest common factor of aand b.

See also

BICONDITIONAL

.

Julia set See

FRACTAL

.

290 Julia set