Алгоритм Евклида
Когда необходимо вычислить НОД нескольких чисел можно применить несколько методов: распространение алгоритма Евклида, базирующегося на следующих свойствах: а) НОД (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), что является основой соответствующего итеративного алгоритма.