GCD Euclid's algorithm as solution to the 2-buckets water puzzle I completed an exercise on HackerRank, a site for programming exercises. The problem has been inspired from Die Hard 3 movie. The original problem is like the following.

The problem
You are given two buckets with capacity $5$ (bucket A) and $3$ liters (bucket B); you must obtain exactly $4$ liters of water (there is a fountain somewhere). The procedure is the following:


*

*fill bucket A from the fountain completely: A=5,B=0

*fill the bucket B with the water in bucket A: B=3 and A=2

*empty bucket B: A =2, B=0

*fill bucket B with the water in A: A=0, B=2

*refill bucket A from the fountain: A=5, B=2

*fill bucket B with the water in A: A=4, B=3
Now changing the capacity values (let me call them c1 and c2) of the $2$ buckets and the desired final value (let me call it d), sometimes this problem has a solution sometimes it doesn't.

The solution
It turns out it has a solution when two conditions are satisfied (at least according to the HackerRank website and some users):


*

*at least one of the buckets has a capacity larger than the final desired quantity: c1>d OR c2>d

*calling gcd the greatest common divisor between c1 and c2,  it must be that the reminder of the division d/gcd is 0.


I discovered Euclid's algorithm and this implementation in the C programming language and everything worked out. The Euclid's algorithm to find the greatest common divisor, has the following procedure (let me assume c1>c2 and let r be the reminder at each step of the division c1/c2):
while c2>0 do:
    r = c1 % c2
    c1 = c2
    gcd = c2
    c2 = r
return gcd

gcd variable will hold the value representing the greatest common divisor.

My questions
However I am left with two questions, one about the problem and the other about Euclid's algorithm (they might be related):


*

*why does the second condition (the one about the greatest common divisor) guarantee to tell if a solution exists for such a problem? Can anyone make the passage explicit?

*Can you make explicit why Euclid's algorithm results in the GCD? It looks like magic to me.


Sorry if my question is quite long but I tried to give every piece of information.
 A: All numbers are integers in the following unless stated otherwise.

Answer to your first question:
Assume that $\gcd(c_1,c_2)= a$ then by Bézout´s identity we have that there exists $m,n\in\mathbb{Z}$ such that
$$
a=n\cdot c_1+ m\cdot c_2, 
$$
and the fact that $\frac{d}{a}$ leaves $0$ as a remainder can be phrased as
$$
d=k\cdot a,\qquad k\in\mathbb{Z}.
$$ 
Putting these two together means
$$
d= k\cdot n\cdot c_1+k\cdot m\cdot c_2
$$
to make this a bit cleaner let $\tilde{n}=k\cdot n$ and $\tilde{m}=k\cdot m$ so
$$
d=\tilde{n}\cdot c_1+\tilde{m}\cdot c_2, \qquad \tilde{n},\tilde{m}\in\mathbb{Z}
$$
So we could get $d$ as a linear combination of $c_1$ and $c_2$, translate this as we could get $d$ by taking a number of times $c_1$ and a number of times $c_2$. Observe that these numbers can be negatives as well so put a couple of $c_1$s in and remove some $c_2$s is also possible. 
Now for the second question:
Assume that $a,b\in\mathbb{Z}$. It is not hard to see that then 
$$
b>0 \ \ \text{and} \ \ \ b\mid a\Rightarrow \gcd(a,b)=b
$$
Another ingredient is the following fact, if $b\neq 0$ then 
$$
a=b\cdot q+r\Rightarrow \gcd(a,b)=\gcd(b,r)
$$
where $b>r$. I chellenge you to try to prove this :)
Having these in mind the Eucledean algorithm is as follows:
$$
a=bq_1+r_1 \qquad 0\le r_1< b
$$
$$
b=r_1q_2+r_2 \qquad 0\le r_2< r_1
$$
$$
r_1=bq_3+r_2 \qquad 0\le r_2< r_3
$$
and so on. This will terminate after a while since the remainders are getting smaller and smaller and at some point you will reach $r_{n+1}=0$.
This gives us the following chain of equalities:
$$
\gcd(a,b)=\gcd(b,r_1)=\gcd(r_1,r_2)=\ldots=\gcd(r_{n-1},r_n)=\gcd(r_n,0)=r_n
$$
I hope this helped a bit.
