# Water Jug Problem

only thing we should proof is this:

then for a GCD `g`, from `gx` and `gy`,
we can and only can reach every `z` in `{i * g | i in [0, x + y] }`

now, let's see how to proof (1).
let x be the less one, and y the greater one.
then fill the two jug to full, we have `x` and `y` water each and `x + y` water in total.
then we pour out x water each time until we can't.

now we have these different z:

finally we have `y % x` water left, we pour it into the x jug,
then fill the y jug to full.
now the two jugs have `y % x` and `y` water separately,
and `y + y % x` water in total.
then we pour from y jug into x jug until the x jug is full,
afterwards do the same thing like before,
to pour out x water each time until we can't.

finally we get `(y + y % x) % x = (y % x + y % x) % x = (2y) % x` water left.

now we have these different z:

do this x times, we get z:

then you see `(xy) % x = 0`, and

set `{ y % x, (2y) % x, (3y) % x, ... , ((x-1)y) % x }` just equals to `{ 1, 2, 3, 4, 5, ... , x - 1 }` . (2)

proof for (2):
modulo x could get x - 1 different results at most exclusive 0, that's 1,2,3,...,x-1.
we have x - 1 expressions, suppose there is two same,
let a != b in [1, x-1] and `(ay) % x = (by) % x`,
then we get `((a - b)y) % x = 0`,
then `((a - b) % x) * (y % x) = 0``(a - b) % x = 0`.
for `1 <= a, b <= x - 1`, so we get `a = b`. it's impossible.

so we can get any z in [0, x + y] water for coprime x and y.