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$.


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$.
