Water and Jug Problem

/*
Forget about two jugs pouring between each other, which may make you confused.
Let's make it simple: assuming we have one big enough bucket and two cups with volume x and y, respectively. 
Now we want to perform a series of operation -- pouring water in and out only by those two cups.
Somehow, there will be only z water left in this big bucket eventually. Then the equation will be:

z = m * x + n * y

m means using cup-x m times. If m is positive, it means pouring in. Otherwise, it's pouring out.

For example, 4 = (-2) * 3 + 2 * 5, which means you pour in water twice with cup-5 and pour out water twice with cup-3. 
Talk back to the question, it's like we first fill jug-5, pour water to jug-3 from jug-5, empty jug-3, 
pour the remaining 2 water into jug-3 from jug-5, fill jug-5 again, pour water into jug-3 from jug-5, empty jug-3, 
then we have only 4 water left in jug-5. It's exactly fill jug-5 twice and empty jug-3 twice.

Now the question is, can we find those two m and n exist?

The answer is YES. Here we need a little math -- Bezout's identity, which is:

We can always find a and b to satisfy ax + by = d where d = gcd(x, y)

So, everything is clear, if z % d == 0, then we have (ax + by)* (z/d) = d*(z/d) => (a*z/d)*x + (b*z/d)*y = z, which means m and n exist.

*/
public class Solution {
    public boolean canMeasureWater(int x, int y, int z) {
        if(x+y < z) return false;
        if(x == z || y == z || x+y == z) return true;
        return z % GCD(x, y) == 0;
    }
    
    public int GCD(int x, int y) {
        if(y == 0) return x;
        return GCD(y, x%y);
    }
}

Proof for Bezout's identity:
https://en.wikipedia.org/wiki/Bézout%27s_identity
Bézout's identity (also called Bézout's lemma) is a theorem in elementary number theory: let x and y be nonzero integers and let d 
be their greatest common divisor. Then there exist integers a and b such that
a*x + b*y = d 

In addition,
the greatest common divisor d is the smallest positive integer that can be written as ax + by
every integer of the form ax + by is a multiple of the greatest common divisor d.

Bezout's identity is based on the property of Euclidean division, namely: that dividing a positive integer p by a positive integer q
yields a reminder greater than or equal to zero and strictly less than q
i.e. p = nq + r, 0 <= r < q

To begin the proof of Bezout's identity, let d be the smallest positive integer of the form ax + by. Specifically,
let d = sx + ty
let n = ax + by n > d
if n is not divisible by d, then according to Euclidean division,
n = qd + r, 0 < r < d
r = n - qd = ax + by - q(sx + ty) = (a-qs)x + (b-qt)y
which of course is the form ax + by
But r < d which violates the original premise that d is the smallest number in that form, therefore r = 0 and 
n is divisible by d

Since n can be any number of the form ax + by, lets look at the following example:
n = 1*x + 0*y = x
n = 0*x + 1*y = y
Therefore, d is a common divisor to both x and y

If there exists another common divisor(c) of a and b,then it also divides d
x = pc
y = qc
d = sx + ty = pcs + qct = c(ps + qt)
if c divides d, then c <= d
Therefore, (finally) d is the greatest common divisor.


Proof for GCD:
The greatest common divisor (gcd) of two positive integers is the largest integer that divides both without remainder. 
Euclid’s algorithm is based on the following property: if p>q then the gcd of p and q is the same as the gcd of p%q and q. 
p%q is the remainder of p which cannot be divided by q, e.g. 33 % 5 is 3. This is based on the fact that the gcd of p and q also 
must divided (p-q) or (p-2q) or (p-3q). Therefore you can subtract the maximum of a multitude q from p which is p%q.