Задача 8.

(алгоритм Евклида) Рассмотрим следующий процесс. Пусть $(a,b)$ — пара положительных чисел такая, что $a\geqslant b$. Она заменяется на пару $(b,r)$, где $r$ — остаток от деления $a$ на $b$. Пара $(b,r)$ заменяется по тому же правилу, и так далее. Процесс завершается, когда получается пара вида $(d,0)$. Покажите, что 1) процесс всегда завершается; 2) $d=НОД(a,b)$.