Euclidean algorithm?

Question

Prove that if the Euclidean algorithm is applied to integers m and n, not both 0, then the last nonzero remainder is gcd(m,n)

Answer 1

write n=qm+r with n>m>r. Then gcd(n,m)=gcd(m,r). So do it again.
When you get to n'=q'm', then m'=gcd(m',n') and since all the gcd's going backwards are equal, m'=gcd(n,m).