Proof of Extended Euclidean Algorithm? There exist $x$ and $y$ such that: $\gcd (a,b) = xa + yb$.
Why is this true? What's the reasoning behind it?

To understand why "there exists numbers $x$ and $y$ such that $\gcd(a,b)=xa+yb$" you should understand the Euclidean Algorithm:
http://en.wikipedia.org/wiki/Euclidean_algorithm
Euclidean Algorithm:
Let's see what it's all about. 
Given two numbers $a,b$ either $b$ divides $a$, denoted $b|a$, in which case $a=bq$ for $q\in \mathbb{Z}$; or $b$ does not divide $a$. If $b$ does not divide $a$, then there exists unique numbers $r$ and $q$ such that $a=bq+r$ with $0\le r\lt b$ (this includes the case when $b|a$, i.e. $r=0$). This is one of the first theorems addressed in most number theory texts and is key to the Euclidean Algorithm. We do this repeatedly and result with the following:
$a=bq_1+r_1$ where $0\lt r_1\lt  b$
$b=r_1q_2+r_2$ where $0\lt r_2\lt r_1$
$\vdots$ 
$r_{n-2}=r_{n-1}q_{n}+r_{n}$ where $0\lt r_{n-1}\lt r_n$ 
$r_{n-1}=r_nq_{n+1}$
This terminates when $r_{n+1}=0$, which must occur  since each number  $r_i$ decreases by atleast $1$ (termination at $r_n=0$ is formally proven by induction).
The claim is that $r_n=\gcd(a,b)$. Following the algorithm from the top down, we can see that the greatest common divisor of $a$ and $b$ is identical with the greatest common divisor of $b$ and $r_1$:
$\gcd(a,b)=\gcd(b,r_1)=\gcd(r_1,r_2)=\dots =\gcd(r_{n-1},r_n)=r_n$ (The last equality follows from the last line in Euclid's Algorithm)
Result:
Now that we have established $r_n=gcd(a,b)$ and Euclid's Algorithm, all we need to do is rewrite $r_n$ in terms of the previous $r_i's$. Solving the second to last line of the algorithm for $r_n$, we have $r_n=r_{n-2}-r_{n-1}q_{n}$ and substituting for $r_{n-1}$ from the previous line,  we obtain $r_n=r_{n-2}-(r_{n-3}-r_{n-2}q_{n-1})q_n$. Rearranging the terms, we get $r_n=r_{n-2}m+r_{n-3}n$ where $m=1+q_{n-1}q_n$ and $n=q_n$. This process is repeated until we have $r_n=ax+by$  where $x$ and $y$ are integers. This reasoning leads us to conclude that $\gcd(a,b)=ax+by$. 
Example:
Using the Euclideaan Algorithm let's compute the $\gcd(68,20)=4$:
$68=20*3+8$
$20=8*2+4$
$8=4*2$
Using the procedures discussed above, we have $4=20-8*2$ and $8=68-20*3$. A little rearranging and sustitution gives us $4=20-(68-20*3)2$ which yields $4=20*7-68*2$.
Hope this helps!
