Популярные ответы
Делителем целого числа m называется любое целое число q, на которое m делится без остатка.
Общим делителем нескольких чисел называется такое число, которое является делителем каждого из них. Например, числа 36, 60, 42 имеют общие делители 2, 3 и 6.
Наибольший общий делитель (НОД) для двух целых чисел m и n — это наибольшее из целых чисел, на которые m и n делятся без остатка. Например: для чисел 70 и 105 наибольший общий делитель равен 35.
Для наибольшего общего делителя чисел m и n применяются следующие математические обозначения:
- НОД(m, n)
- (m, n)
- gcd(m, n) — от англ. Greatest Common Divisor.
Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n отлично от нуля.
Понятие наибольшего общего делителя естественным образом обобщается на наборы из более чем двух целых чисел.
Чтобы найти наибольший общий делитель (НОД) нескольких чисел надо:
- Представить каждое число как произведение его простых множителей, например:
360 = 2 · 2 · 2 · 3 · 3 · 5.
- Записать степени всех простых множителей:
360 = 2 · 2 · 2 · 3 · 3 · 5 = 23 · 32 · 51.
- Выписать все общие делители (множители) этих чисел.
- Выбрать наименьшую степень каждого из них, встретившуюся во всех произведениях.
- Перемножить эти степени.
Однако такой метод поиска НОД весьма трудоемок. С древности известен более удобный метод нахождения НОД, называемый алгоритмом Евклида.
- Пусть m>n. Найдем остаток r от деления m на n.
- Если r = 0 (т.е. m делится на n), то НОД(m, n) = n.
- В противном случае вместо чисел m и n надо взять числа n и r и перейти к п. 1.
- Алгоритм завершается, когда очередной остаток от деления окажется равен нулю.
Источники:
Дополнительно на Геноне: