Задача 8.

(Euclidean algorithm) The Euclidean algorithm proceeds in a series of steps. Let $(a,b)$ be a pair of positive numbers such that $a\geqslant b$. The first step is to consider a pair $(b,r)$, where $r$ is the remainder from division $a$ by $b$. In the next step, insead of the pair $(b,r)$ we consider a pair $(r,r_1)$ using the same rule. We stop once we get a pair of the type $(d,0)$. Show that 1) the process has an end; 2) $d=GCD(a,b)$.