Вообще говоря, остановится он гораздо быстрее (подумайте, почему?), а примером самого медленного схождения является отыскание с его помощью наибольшего общего делителя у двух соседних чисел последовательности Фибоначчи.
Кстати, попробуйте и так доказать, что такие два числа обязаны быть взаимно просты.
Алгоритм Евклида – алгоритм для нахождения наибольшего общего делителя двух целых чисел a и b (общей меры двух целочисленных величин), впервые описанный древнегреческим математиком Евклидом в «Началах» (III в. до н. э.) – своем главном труде, посвященном геометрии и теории чисел.
Идея алгоритма состоит в том, что мы пытаемся «исчерпать» меньшей величиной
(пускай это будет число b) большую – меньшая, скорее всего, уложится в большей некоторое целое число раз с каким-то остатком, величина которого строго меньше
той величины, которой мы черпали.
Ну это и понятно – если бы она была «нестрого меньше», то мы смогли бы ее зачерпнуть еще один полный раз. Затем мы уменьшаем «кандидата» на общую меру, черпая теперь уже величиной остатка. Поскольку оба числа у нас по условию целые, то в худшем случае такой общей мерой будет единица – тогда говорят, что числа a и b взаимно просты, или что НОД (a, b) = 1 – иначе НОД (a, b) будет равен последнему ненулевому остатку в организованной таким образом процедуре.
Следовательно, алгоритм гарантированно останавливается не позднее, чем через b шагов.