5 класс · Делимость натуральных чисел

НОД. Взаимно простые числа

Общий делитель

Все натуральные числа имеют хотя бы один общий делитель — число 1. Но у некоторых чисел есть и другие общие делители. Например, у чисел 24 и 16, помимо 1, есть общие делители 2, 4 и 8. Самый большой из них — 8. Его называют наибольшим общим делителем чисел 24 и 16 и записывают так: $\text{НОД}(24,16)=8$.

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

Наибольший общий делитель (НОД) двух и более чисел — это самое большое число, на которое делится каждое из данных чисел.

Способ через разложение на множители

Найдём $\text{НОД}(1968,\,2520)$. Разложим оба числа на простые множители и сравним разложения:

$1968 = 2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 41$

$2520 = 2\cdot 2\cdot 2\cdot 3\cdot 3\cdot 5\cdot 7$

Выделим множители, которые встречаются в обоих разложениях: тройка двоек $2\cdot 2\cdot 2$ и одна тройка $3$ — этих множителей поровну хватает у обоих чисел. Четвёртой двойки во втором числе уже нет, а множители 41, 3 (второй) и 5, 7 — не общие.

Перемножим общие множители: $\text{НОД}(1968,2520) = 2\cdot 2\cdot 2\cdot 3 = 24$.

Проверь это разложение шаг за шагом в блоке «НОД по разложению» справа.

🧠 Алгоритм нахождения НОД через разложение на простые множители:

Разложить данные числа на простые множители.
Выписать в виде произведения все общие простые множители — те, что есть у всех чисел, взятые столько раз, сколько поместится в каждом из чисел.
Если нужно, найти значение полученного произведения.

Пример 1. НОД сразу нескольких чисел

Способ разложения на множители работает не только для двух чисел, но и для любого их количества. Найдём $\text{НОД}(60,72,96)$:

$60=2\cdot 2\cdot 3\cdot 5;\quad 72=2\cdot 2\cdot 2\cdot 3\cdot 3;\quad 96=2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 3$

Во всех трёх разложениях гарантированно найдутся только две двойки и одна тройка (больше двоек нет у 60, а больше троек — у 72 и 96). Значит,

$\text{НОД}(60,72,96) = 2\cdot 2\cdot 3 = 12$

Пример 2. Когда общих множителей нет

Найдём $\text{НОД}(56,81)$:

$56 = 2\cdot 2\cdot 2\cdot 7;\qquad 81 = 3\cdot 3\cdot 3\cdot 3$

В этих двух разложениях нет ни одного одинакового множителя — общих простых множителей просто нет.

Взаимно простые числа — это числа, у которых нет общих простых множителей. Наибольший общий делитель взаимно простых чисел всегда равен 1: $\text{НОД}(56,81)=1$.

Загляни в блок «НОД по разложению», чтобы увидеть, что здесь совпадать попросту нечему, и попробуй сам подобрать взаимно простые пары в блоке «Взаимно простые?» справа.

Пример 3. Когда одно число делится на другое

Найдём $\text{НОД}(45,450)$:

$45 = 3\cdot 3\cdot 5;\qquad 450 = 2\cdot 3\cdot 3\cdot 5\cdot 5$

Все множители числа 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.
Если одно число делится на другое, то их НОД равен меньшему из них.
Способ разложения годится для любого количества чисел, не только для двух.

Закрепи в практике

Каждый вариант — с новыми числами; разбор после каждого ответа.

Перейти к практике