1. Доказать свойства НОД. 2. Реализовать процедуры нахождения НОД двух чисел, реализующие: a. алгоритм Евклида «с вычитанием» (свойства 1, 3); b. алгоритм Евклида «с делением» (свойства 1, 4); c. «бинарный» алгоритм Евклида (свойства 1, 3, 5, 6). 3. Провести сравнительный анализ алгоритмов, выполнить оценку временной сложности. 4. Реализовать эффективный вариант нахождения НОД четырех, пяти, n чисел. Пусть есть два отрезка. Их длины a и b – целые числа (далее, говоря о числах, считаем их всегда целыми). Скажем, a=2322, а b=654. Если, например, отложить на прямой отрезок a, затем, в обратном направлении, три раза b, то получим отрезок длиной 360 (рис. 1). Действительно, a+b•(–3)=2322+654•(–3)=360. Можно получить и отрезок меньшей длины. Действуем так: a•2+b•(–7)= 2322•2+654•(–7)=66 – два раза откладываем отрезок a и семь раз отрезок b в обратном направлении. Возникает, как минимум, четыре вопроса. 1. Какую наименьшую длину удастся получить, «орудуя» заданными отрезками a и b? 2. Как это сделать, сколько раз взять отрезок a и сколько раз отрезок b? 3. Какой длины отрезки отмеряются с помощью a и b? 4. Если отрезок заданной длины отмеряется, то, как это сделать?