К>Вот например, такой вопрос: оценка времени вычисления.
К>В частности, на каких числах НОД вычисляется дольше всего?
Число шагов деления в алгоритме Евклида -- логарифмическое с
основанием равным золотому сечению. Это следует из такого
утверждения: если меньшее из чисел, для которых запущен Евклид,
меньше F_{k+1} (F_k -- числа Фибоначчи), то число шагов деления
не больше k (теорема Ламэ, кажется).