Общие делители и кратные. НОД и НОК

Есть 12 красных и 18 синих карточек. Нужно использовать их все и сделать наборы так, чтобы в каждом было одинаковое количество красных и одинаковое количество синих карточек. Число наборов должно делить и 12, и 18. А если два сигнала повторяются через 12 и 18 минут, время их следующего совпадения должно быть кратно обоим числам. Эти две задачи ведут к разным понятиям.

Общие делители и НОД

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

Делители 12 — числа 1, 2, 3, 4, 6, 12. Делители 18 — числа 1, 2, 3, 6, 9, 18. Общие делители — 1, 2, 3, 6, поэтому $НОД (12, 18) = 6$ . Наибольший общий делитель существует: общих делителей конечное количество и среди них всегда есть 1.

Два ряда делителей чисел 12 и 18; общие значения 1, 2, 3, 6 соединены, наибольшее — 6. — Рис. 1. НОД выбирают среди делителей обоих чисел, а не только меньшего числа.

В задаче с карточками можно сделать шесть одинаковых наборов. В каждом будет $12 : 6 = 2$ красные карточки и $18 : 6 = 3$ синие. Сделать больше одинаковых наборов с использованием всех карточек нельзя: их количество должно быть общим делителем, а большего, чем 6, нет.

Два натуральных числа называют взаимно простыми, если их НОД равен 1.

Например, 8 и 15 взаимно простые, хотя каждое из них составное. Название относится к отсутствию общего делителя больше 1, а не к простоте самих чисел.

Общие кратные и НОК

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

Кратные 12: 12, 24, 36, 48, 60, 72… Кратные 18: 18, 36, 54, 72… Первое положительное совпадение — 36. Поэтому $НОК (12, 18) = 36$ . Нуль тоже общее кратное, но при поиске НОК его исключают: по определению требуется положительное число.

На двух шкалах отмечены моменты сигналов через 12 и через 18 минут; первое совпадение после нуля — 36 минут. — Рис. 2. Совпадения происходят в общих кратных; НОК указывает первое из них после начала отсчёта.

Если сигналы прозвучали одновременно в начале, снова они совпадут через 36 минут. Для этого вывода важно общее начало: если второй сигнал запустили позже, одной величины НОК недостаточно. Условие задачи определяет, можно ли использовать правило.

Поиск через простые множители

Для небольших чисел удобно выписать делители и кратные. Для больших помогает разложение на простые множители. Пусть $12 = 2 \cdot 2 \cdot 3$ , а $18 = 2 \cdot 3 \cdot 3$ . Общий делитель может содержать только множители, которые есть в обоих разложениях: одну двойку и одну тройку. НОД равен $2 \cdot 3 = 6$ .

Общее кратное должно содержать достаточно множителей для каждого исходного числа. Для 12 нужны две двойки, для 18 — две тройки. Самое небольшое подходящее произведение — $2 \cdot 2 \cdot 3 \cdot 3 = 36$ . Если использовать степени, для НОД берут меньшую степень каждого общего простого множителя, для НОК — большую степень каждого встречающегося простого множителя.

Разберём 24 и 36: $24 = 2^{3} \cdot 3$ , $36 = 2^{2} \cdot 3^{2}$ . Тогда $НОД (24, 36) = 2^{2} \cdot 3 = 12$ , а $НОК (24, 36) = 2^{3} \cdot 3^{2} = 72$ . Проверка: 12 делит оба числа; 72 делится и на 24, и на 36.

Быстрая связь и её границы

Для двух натуральных чисел $a$ и $b$ верно:

НОД (a, b) \cdot НОК (a, b) = a \cdot b .

В разложениях сумма меньшего и большего показателей каждого простого множителя равна сумме двух исходных показателей. Поэтому произведения совпадают. Для 24 и 36 получаем $12 \cdot 72 = 24 \cdot 36 = 864$ , и при известном НОД можно найти НОК делением произведения на НОД.

Произведение двух чисел не всегда является их НОК. Для 12 и 18 произведение равно 216, но первое положительное общее кратное — 36. Произведение совпадает с НОК у взаимно простых чисел, потому что их НОД равен 1. Связь выше относится именно к двум числам; автоматически переносить её на три числа нельзя.