Алгоритм Евклида

Когда необходимо вычислить НОД нескольких чисел
можно применить несколько методов:
распространение алгоритма Евклида, базирующегося на следующих свойствах:
а) НОД (0,…,0,a,0,…,0)=a;
b) НОД (a1,…,ai,…,an)=
НОД (a1 mod ai ,…,ai,…,an mod ai) при ai≠0.
2) метод заключается в повторном применении алгоритма Евклида для двух целых чисел.
Он основан на следующем свойстве:
НОД (a1,…,an)=НОД(a1,НОД(a2,…,an)),
которое порождает рекурсивный алгоритм
вычисления НОД. Именно
НОД(a1,…,an)=НОД(НОД(a1,a2),a3,…,an),
что является основой соответствующего
итеративного алгоритма.

Теорема Дирихле. Если a и b два натуральных числа, выбранные случайно, то вероятность того, что они взаимно простые равна
Теорема Ламе. Число итераций, необходимых для
вычисления НОД(а,b), а>b>0, мажорируется
5-кратным числом десятичных знаков наименьшего из этих двух чисел. Более формально, если n является искомым числом итераций, то
или
Главный результат – сложность алгоритма Евклида
для целых чисел логарифмическая по отношению
к наименьшему из двух чисел. В оценке Ламе
коэффициент 5 оптимален, но мажорирующая
функция (O(log b)) таковой не является.