К содержимому

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

Опубликована · Ключевая · Обновлена: 13.11.2026 23:41

Автор: Александр Смирнов · Редакторы: Юрий Карпенко

Условие

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

Основная идея алгоритма содержится в следующем математическом свойстве 
\[ \text{НОД}(a, b) = \text{НОД}(b, r) \]
где $r$ — остаток от деления $a$ на $b$.

Таким образом, алгоритм состоит из двух шагов: 

1) для пары чисел $a\geq b$ если $b \neq 0$ находится остаток $r$ от деления $a$ на $b$;

2) пара $a \geq b$ меняется на пару $b \geq r$. 

Процесс повторяется до тех пор, пока остаток не станет равен нулю. Последний ненулевой остаток и будет искомым НОД.

Пример работы. Найдем $\text{НОД}(1071, 462)$:

\[\begin{aligned} 1071 &= 462 \times 2 + 147 \\ 462 &= 147 \times 3 + 21 \\ 147 &= 21 \times 7 + 0 \\ \end{aligned}\]

Последний ненулевой остаток — 21. Следовательно 
\[ \text{НОД}(1071, 462) = 21. \]

Оцените сложность темы "алгоритм Евклида" числом от 1 до 5: 1 - просто; 5 - сложно.