I created a proof of the euclidean algorithm and since I'm not really familiar with the field of discrete mathematics I'm asking for a revision :
Having two natural numbers $a$ and $b$ we follow this procedure :
$1)$ If $a=b \implies GCD(a,b) = a = b \:$ and stop.
$2)$ First of all I write :
$$a = GCD(a,b)\cdot q \\ b = GCD(a,b)\cdot r$$
so because of definition $q$ and $r$ are coprime.
Say $\max(a,b) = a$ then take :
$$a' = a - b = GCD(a,b)\cdot q - GCD(a,b)\cdot r = GCD(a,b)\cdot (q-r)$$
So it's sure that :
$$GCD(a',b) = GCD(a,b)\cdot s $$
if $s = 1$ then the proof is complete, this is equivalent to $q-r$ and $r$ being coprime :
So suppose $q-r$ and $r$ a being not coprime then $q-r = k\cdot w\:$ and $\:r = k\cdot p \:$ (with $k>1$), but then :
$$ q = k\cdot w + r \implies \frac{q}{r} = \frac{k\cdot w + r}{k\cdot p} = \frac{w}{p} + 1 = \frac{w+p}{p} $$
This is a contradiction because $q$ and $r$ are coprime , but $p<r$ and $w+p<q$, so $q-r$ and $r$ are also coprime , then :
$$GCD(a',b) = GCD(a,b) $$
$3)$ Reiterate the first two steps (with $a'$ instead of $a$ in this case ) until $1)$ is true
Besides , the procedure has a finite number of steps , because the algorithm produces always a pair $(a,b) = ( GCD(a,b)\cdot q, GCD(a,b)\cdot r) $ and since either $q$ or $r$ is reduced at every iteration , then the pair will become $(GCD(a,b),GCD(a,b))$ at the end of the procedure (taking for example the condition of $\max(a,b) = a $ in $2)$ we have $a' < a $ ) .
The way I'm writing it can be confusing because it's a mixture of the steps of the algorithm and the proof of it , but somehow I find it clearer .