 Solution

At any division step $u=qv+r$, an integer divides both $u,v$ exactly when it divides both $v,r$: one direction uses $r=u-qv$, and the other uses $u=qv+r$. HenceStarting with $r_0=a$, $r_1=b$, the Euclidean division producesThe nonzero remainders form a strictly decreasing sequence of positive integers. Such a sequence must terminate, since there are only finitely many positive integers below $b$. Suppose $r_N$ is the last nonzero remainder, so $r_{N+1}=0$. The unchanged greatest common divisor at each step givesThe final equality holds because the positive common divisors of $r_N$ and $0$ are precisely the positive divisors of $r_N$. This proves both termination and correctness of the Euclidean algorithm.