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

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

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

Creative Commons Attribution/Share-Alike License 3.0 (Unported)

Этот материал распространяется на условиях лицензии Creative Commons Attribution/Share-Alike License 3.0 (Unported). Это означает, что вы можете размещать этот контент на своем сайте или создавать на его основе собственный (в том числе и в коммерческих целях), при условии сохранения оригинального лицензионного соглашения. Кроме того, Вы должны отметить автора этой работы, путем размещения HTML ссылки на оригинал работы https://planetcalc.ru/323/. Пожалуйста оставьте без изменения все ссылки на других авторов данной работы или работы, на основе которой создана данная работа (если таковые имеются в спроводительном тексте).

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

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

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

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

НОД
 

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

Комментарии