Математика • 7 класс

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

Алгоритм Евклида – способ нахождения наибольшего общего делителя двух чисел путём последовательного деления.
1. Из двух данных чисел выбрать большее и разделить его на меньшее.
2. Если числа разделились без остатка, то меньшее число – НОД.
3. Если числа разделились с остатком, то делим делитель на остаток.
4. Продолжаем алгоритм, пока числа не разделятся нацело, в этом случае делитель – НОД.
Пример. Найдите НОД (451, 287).
451 = 287 $\cdot$ 1 + 164;
287 = 164 $\cdot$ 1 + 123;
164 = 123 $\cdot$ 1 + 41;
123 = 41 $\cdot$ 3 + 0;
НОД (451, 287) = 41.