[![enter image description here](https://i.stack.imgur.com/byhaM.png)](https://i.stack.imgur.com/byhaM.png)

I tried to prove it with linear combination.

Also other information,

* $h\*\gcd(m, n)=h\*am+h\*bn$
* At each iteration $i$, $y\_i=x\_iq+r$
* Last iteration $t$, so $x\_t=\gcd(m, n)$.

Base case: Iteration t. $x\_t=h\_t\*\gcd(m, n)=h\_t\*am+h\_t\*bn$. Last iteration, $x\_t=\gcd(m, n)$, so $h\_t = 1$. Hence, $\gcd(m, n)=am+bn$

> 
> I don't know how to prove that m, n are positive integers and a, b are integer.
> 
> 
> 

Assume iteration k, $x\_k=h\_k\*\gcd(m, n)=h\_k\*am+h\_k\*bn$, for some integer h, $x\_k$ is a multiple of gcd.

We need to prove $x\_{k+1}=h\_{k+1}\*\gcd(m, n)=h\_{k+1}\*am+h\_{k+1}\*bn$.

> 
> I don't know is that correct, if it is wrong, please tell me
> 
> 
> 

Also, I don't know is this prove correct.