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

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

Первое число

Второе число

Рассчитать

НОД

 

 Ссылка  Сохранить  Виджет

Алгоритм Евклида для нахождения НОД

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

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

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