Глава 8. Теория чисел

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

Когда говорят «число делиться», то имеют в виду, что оно делиться без остатка. Так A делиться на B, лишь в том случае, если остаток от их деления равен нулю. На этом свойстве основывается понятие наибольшего общего делителя (НОД). НОД двух чисел – это наибольший из всех их общих делителей.

Одним из простейших алгоритмов нахождения наибольшего общего делителя является Алгоритм Евклида. Он назван в честь известного древнегреческого математика, автора первого из дошедших до нас теоретических трактатов по математике – Евклида Александрийского. Выделяют два способа реализации алгоритма: методом деления и методом вычитания. Рассмотрим отдельно каждый из них.