Euclidean Algorithm 
The Euclidean Algorithm is based on the move from a pair $(m,n)$, where $m>n$, to the pair $(m-n,n)$ which is then ordered so that the larger number is listed first. If we start from two numbers $a>b$ show that at every next stage the two obtained numbers are integral linear combinations of $a$ and $b$. Those are numbers of the form $ka+rb$ , where $k$ and $r$ are integers. Conclude that $\gcd(a,b)$ is the smallest positive integral linear combination of $a$ and $b$.

 A: You can keep subtracting $n$ until the first number becomes smaller than $n$ (assuming $n>0$, otherwise the greatest common divisor is $m$).
This is the “division with remainder”: $m=nq+r$, where $0\le r<n$.
Now, given $a>b>0$, we can proceed just like old Euclid did (with different terminology). Set $r_0=b$ and do the division like before:
$$
a=r_0q_1+r_1,\qquad 0\le r_1<r_0
$$
Note now that the pairs $(a,b)=(a,r_0)$ and $(r_0,r_1)$ have the same common divisors; we are done if $r_1=0$, otherwise we can repeat:
$$
r_0=r_1q_2+r_2,\qquad 0\le r_2<r_1
$$
and proceed in the same way until we get $0$ as remainder: this is certain to happen, because the successive remainders decrease. We even have a bound on the number of steps: it is $b$. Actually the bound can be refined, but we just need to know the algorithm stops.
At each stage, the greatest common divisor of the pair $(r_{k-1},r_k)$ is the same as the greatest common divisor of the pair $(r_k,r_{k+1})$. So if we say that in $n$ steps we find the last nonzero remainder, that is, $r_{n-1}=r_nq_{n+1}+0$, the considerations above tell us that $r_n$ is the greatest common divisor of $a$ and $b$.
Now we want to get as fast as possible that $r_n=as+bt$ for some integers $s$ and $t$. We can do by induction on $n$ (the number of steps for getting at the greatest common divisor).
If $n=0$, then $a=bq_1$ and so $b=\gcd(a,b)$ and $b=a\cdot0+b\cdot1$. Thus the base step is done.
Suppose $n>0$. We need to find a pair of numbers for which the algorithm takes $n-1$ steps. But we already have them: the algorithm from $A=b$ and $B=r_1$ proceeds in exactly the same way, with the only difference it takes one step less! Then the induction hypothesis gives us
$$
r_n=bs'+r_1t'
$$
for some integers $s'$ and $t'$. But the first step of the algorithm says $r_1=a-bq_0$, so
$$
r_n=bs'+(a-bq_0)t'=at'+b(s'-q_0t')
$$
and we are done with $s=t'$ and $t=s'-q_0t'$.
Now we have all the tools for characterizing the greatest common divisor as the least positive integral linear combination of $a$ and $b$.
We have proved that the greatest common divisor $d=\gcd(a,b)$ is an integral linear combination. Suppose $c=au+bv$ is a positive integral linear combination. Since $a=a'd$ and $b=b'd$ for some integers $a'$ and $b'$, we have
$$
c=a'du+b'dv=d(a'u+b'v)
$$
and $a'u+b'v$ is positive, hence $a'u+b'v\ge1$. Therefore $c\ge d$.
Note that we have proved more: every (positive) integral linear combination of $a$ and $b$ is a multiple of $\gcd(a,b)$. Note also that the Euclidean algorithm provides a way to compute explicitly the integers $s$ and $t$.
A: The proof is by iteration. Notice, in each step the first larger number gets smaller. But, this cannot go on without end as numbers are finite. Consequently, there is a smallest number which the algorithm reaches. I'm not sure what you're asking generally so I'll illustrate the method for now:
\begin{align}
(16,10) &= (a,b) \\
(6,10) \mapsto (10,6) &= (b,a-b) \\
(4,6)\mapsto (6,4) &= (a-b, b-(a-b)) = (a-b,2b-a) \\
(2,4) \mapsto (4,2) &= (2b-a, (a-b)-(2b-a)) = (2b-a, 2a-3b) \\
\end{align}
Now that $2\mid 4$ I halt and observe $gcd(16,10)=2$ and $2 = 2a-3b$ or,
$2= 2(16)-3(10)$. Notice the "positive" refers to $2$ not the coefficients $k,r$ in the $\mathbb{Z}$-linear combination. Usually the euclidean algorithm based on remainders is faster, but here it's about the same:
\begin{align}
(16,10) &= (a,b) \\
(10, 6)&=(b,a-b) \\
(6, 4) &= (a-b,b-(a-b)) = (a-b,2b-a) \\
(4,2) &=(2b-a, a-b-(2b-a)) = (2b-a,2a-3b).
\end{align}
