§ 6. Наименьшее общее кратное

Число 72 делится нацело и на 8, и на 12. Про такое число говорят, что оно является общим кратным чисел 8 и 12. Общих кратных у пары чисел сколько угодно: для 8 и 12 подойдут также 24, 48, 96 и любое следующее. А вот самое маленькое из них ровно одно — им и занимается этот параграф.

Выпишем подряд кратные числа 6 и кратные числа 9 и посмотрим, какие числа попали в оба ряда сразу (рис. 1). Совпали 18, 36, 54 — это общие кратные чисел 6 и 9. Слева стоит самое маленькое из них.

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

Для пары чисел a и b такое число записывают коротко: НОК (a; b). Для нашего примера НОК (6; 9) = 18. Точно так же НОК (5; 7) = 35, НОК (14; 21) = 42, НОК (9; 45) = 45.

Первый способ поиска — прямой перебор. Кратные большего числа выписывают одно за другим и каждое проверяют делением на меньшее число; первое подошедшее и есть ответ. Найдём так НОК (15; 20): берём 20, 40, 60. Первые два на 15 не делятся, а 60 : 15 = 4 (рис. 2).

Перебор хорош, пока числа небольшие. С крупными числами удобнее работать через разложение на простые множители. Разложим 45 и 60 и сравним, из чего они собраны (рис. 3): 45 = 3 · 3 · 5 60 = 2 · 2 · 3 · 5 Искомое число обязано делиться на 45, поэтому в нём должны быть все множители числа 45. Оно обязано делиться и на 60, поэтому к ним добавляем те множители числа 60, которых не хватает: двух двоек. Больше добавлять нечего, и лишнего брать нельзя — иначе число вырастет: НОК (45; 60) = 2 · 2 · 3 · 3 · 5 = 180