Все натуральные числа имеют хотя бы один общий делитель — число 1. Но у некоторых чисел есть и другие общие
делители. Например, у чисел 24 и 16, помимо 1, есть общие делители 2, 4 и 8. Самый большой из них — 8. Его
называют наибольшим общим делителем чисел 24 и 16 и записывают так: $\text{НОД}(24,16)=8$.
Найти НОД можно, перебирая делители меньшего из чисел, или делители их разности — эти способы мы уже знаем.
Но есть ещё один, часто более удобный способ — через разложение чисел на простые множители.
Наибольший общий делитель (НОД) двух и более чисел — это самое большое число, на которое
делится каждое из данных чисел.
Способ через разложение на множители
Найдём $\text{НОД}(1968,\,2520)$. Разложим оба числа на простые множители и сравним разложения:
Выделим множители, которые встречаются в обоих разложениях: тройка двоек $2\cdot 2\cdot 2$
и одна тройка $3$ — этих множителей поровну хватает у обоих чисел. Четвёртой двойки во втором числе уже
нет, а множители 41, 3 (второй) и 5, 7 — не общие.
В этих двух разложениях нет ни одного одинакового множителя — общих простых множителей просто нет.
Взаимно простые числа — это числа, у которых нет общих простых множителей. Наибольший общий
делитель взаимно простых чисел всегда равен 1: $\text{НОД}(56,81)=1$.
Загляни во вкладку «НОД по разложению», чтобы увидеть, что здесь совпадать попросту нечему, и попробуй сам подобрать взаимно простые пары во вкладке «Взаимно простые?» справа.
Все множители числа 45 целиком входят в разложение числа 450. Это значит, что 450 делится на 45 без остатка,
а значит 45 и есть наибольший общий делитель этих чисел:
$\text{НОД}(45,450) = 45$
Смотри сам во вкладке «НОД по разложению» — так бывает всегда: если $a$ делится на $b$, то $\text{НОД}(a,b)=b$ (меньшее из чисел).
💡 Из жизни: представь, что у тебя есть 24 синих и 16 жёлтых кубика, и ты хочешь собрать из
них одинаковые наборы — без остатка, чтобы во всех наборах было поровну синих и поровну жёлтых кубиков.
Больше всего таких одинаковых наборов получится ровно НОД(24,16) = 8 штук: по 3 синих и по 2 жёлтых кубика
в каждом.
⚠️ Частые ошибки: во-первых, при повторяющемся множителе иногда по ошибке берут наибольшую
из двух степеней вместо наименьшей — например для $1968=2^4\cdot 3\cdot 41$ и $2520=2^3\cdot 3^2\cdot 5\cdot 7$
могут взять все четыре двойки из первого числа, хотя во втором числе их только три — а НОД делится на оба
числа, поэтому двоек можно взять не больше, чем есть в самом «бедном» разложении. Во-вторых, путают НОД с
произведением всех множителей обоих чисел — в НОД идут только те множители, которые встречаются
в каждом разложении.
🧠 Запомни:
НОД через разложение: разложить числа на простые множители и перемножить только общие.
Общий множитель берётся столько раз, сколько его хватает во всех числах сразу (наименьшее из количеств).
Если у чисел нет общих простых множителей — они взаимно простые, и их НОД равен 1.
Если одно число делится на другое, то их НОД равен меньшему из них.
Способ разложения годится для любого количества чисел, не только для двух.