Наибольшим общим делителем нескольких чисел называется число, которое является делителем каждого из них. То есть это наибольшее число, на которое оба числа a и b делятся без остатка.
Например:
Найдем НОД (21, 14, 42) = 7. Каждое из чисел 21, 14, 42 делится на 7 без остатка и это наибольший общий делитель.
Рассмотрим, как найти НОД на примере.
Чтобы найти НОД нескольких чисел надо (найти НОД (180, 150)):
Представить каждое число в виде простых множителей:
Записать степени всех простых множителей.
Выписать все общие делители (множители) этих чисел.
Выбрать наименьшую степень каждого из них, встретившуюся во всех произведениях.
Наименьшая степень общих делителей 2, 3 и 5.
Перемножить эти степени.
Перемножим 2, 3 и 5:
Итак,
то есть на 30 можно разделить каждое число:
Найти наибольший общий делитель (НОД) чисел 252, 30, 1512.
Представим каждое число в виде простых множителей:
Где возможно, запишем степени полученных множителей:
Выпишем все общие делители:
Выберем наименьшую степень каждого из них: это 21 и 31.
Перемножим эти степени:
Итак, мы нашли наибольший общий делитель:
То есть на 6 можно разделить каждое число без остатка:
Найдем НОД чисел 1050, 630, 2205.
Разложим каждое число на множители:
Где возможно, запишем степени полученных множителей:
Выпишем все общие делители:
Выберем наименьшую степень каждого из них: это 31, 51 и 71.
Перемножим их:
Итак, мы нашли наибольший общий делитель:
НОД (1050, 630, 2205) = 105, то есть на 105 можно разделить каждое число без остатка.
Делимость целых чисел. Понятие делимости
Кратные числа и делители числа
Свойства взаимно простых чисел
Разложение числа на простые множители
Алгоритм Евклида, чтобы найти НОД
Как найти НОД трех и более чисел
Наименьшее общее кратное. Как найти наименьшее общее кратное
Теорема о разложении на множители. Основная теорема арифметики