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

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

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

Чтобы было легче воспринять, проиллюстрируем это примером. Найдем НОД для чисел 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 - простые числа, это действительно так

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


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