homechevron_rightУчебаchevron_rightМатематикаchevron_rightГеометрия

Наибольший общий делитель (НОД) двух целых чисел

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

Сейчас я расскажу вам, как находить наибольший общий делитель двух целых чисел алгоритмом Евклида.

Это довольно просто. Надо строить уменьшающуюся последовательность чисел, первое число которой это максимальное из двух целых, чей НОД мы ищем, второе — соответственно, минимальное из двух целых, а каждое следующее представляет из себя остаток от деления пред-предыдущего на предыдущее. Последний ненулевой член последовательности и есть НОД.

Чтобы было легче воспринять, проиллюстрируем это примером. Найдем НОД для чисел 13 и 17.

1 шаг. Сформируем два первых числа последовательности
17, 13

2 шаг. Третье число последовательности — остаток от деления 17 на 13, то есть 4
17, 13, 4

3 шаг. Четвертое число последовательности — остаток от деления 13 на 4, то есть 1
17, 13, 4, 1

4 шаг. Пятое число последовательности — остаток от деления 4 на 1, то есть 0
17, 13, 4, 1, 0

Перед нулем стоит 1 — последний ненулевой член последовательности. Следовательно, это и есть искомый НОД. С учетом того, что и 13 и 17 — простые числа, это действительно так.

А вот и калькулятор:

PLANETCALC, Наибольший общий делитель (НОД) двух целых чисел

Наибольший общий делитель (НОД) двух целых чисел

НОД
 
Расчет можно сохранить, чтобы использовать в другой раз, extension установить на веб-сайт или share поделиться с друзьями.

Обновление: Как подсказали пользователи, nod(0,x) равен x. Поправлено.

Комментарии