Алгоритм Евклида используется для нахождения наибольшего общего делителя (НОД) пары целых чисел. 2

Последовательность шагов алгоритма: 3

1. На первом шаге нужно разделить большее число на меньшее. 3 Если деление удалось, то есть остаток оказался равен нулю, то меньшее число и будет НОД этих двух чисел. 3 В случае ненулевого остатка необходимо продолжить выполнение алгоритма. 3
2. На втором шаге нужно разделить меньшее из двух данных чисел (первый делитель) на полученный в первом делении остаток. 3 Если при этом делении получится нулевой остаток, то НОД двух данных чисел равен остатку от деления на первом шаге или, что то же, делителю на втором шаге. 3 В случае ненулевого остатка следует продолжить выполнение алгоритма. 3
3. На третьем шаге нужно разделить предыдущий делитель (остаток от предпоследнего деления) на остаток, полученный на предыдущем шаге. 3 В случае получения нулевого остатка НОД будет равен остатку, полученному на предыдущем шаге или, что тоже, последнему делителю. 3 В случае получения ненулевого остатка следует повторить действия на этом шаге вплоть до получения нулевого остатка — в этом случае последний ненулевой остаток или, что то же, последний делитель и будет НОД. 3

Алгоритм Евклида тем эффективнее, чем больше числа, НОД которых следует найти. 3