Пошаговое объяснение:
1) Пусть d - делитель чисел a и b , тогда d - делитель числа
r = a -bq ⇒ d - делитель b и r
2) Пусть к - делитель чисел b и r , тогда к - делитель числа
a = b·q +r ⇒ k -делитель а и b
из 1) и 2) следует , что множества делителей чисел а и b и
b и r совпадают и значит совпадают наибольшие элементы
этих множеств ⇒ нод(а, b) = нод (b , r)
