I1: [Доказать Р(1)] Положить k=1 и согласно п а) выдать доказательство утверждения Р(1).
I2: [k=n?] Если k=n то алгоритм заканчивает работу и требуемое доказательство выдано, если k≠n то:
I3: [доказать Р(k+1)] Согласно пункту б) выдать доказательство того, что если P(1), P(2), …P(k) верны, то что P(k+1) также верно и сделать соответствующий вывод.
I4: [увеличить k] k<--k+1 и перейти на шаг I2
Формула оценки времени выполнения алгоритма Евклида: Tn=(12*Ln(2)/п^2)*Ln(n)